Table of contents


Given problem

Given an array nums = {3, 2, 4, 1, 6}.

How to sort it with the ascending order.


Solution with Heap Sort

  1. Introduction to Heap sort

    Heap sort is a sorting algorithm that uses heap data structure to work. Heap data structure has many variatios such as Binary Heap, and so on.

    Binary heap is a complete tree that all levels has fully nodes, but the last level fills leaf nodes from the left side.

    In heap sort, we will use max heap to implement. Max heap means that the parent nodes’s value is greater than the children nodes’s value.

    Some properties of Binary Heap:

    • The element at index = 0 is the root node of Binary Heap.
    • We have a node at the index = i in an array. Then, we have the left node’s index = 2 * (i + 1) - 1, and the right node’s index = 2 * (i + 1).

  2. Implementation with Heap sort

    • Recursive version

      Before using the property of Binary Heap, we need to convert our array to the Binary Heap format.

      Then, we have the node at index = 0 is the largest node, we swap the node’s value at index = 0 and the node’s value at the last index.

      Decrement the size of an array. Continue doing all above operations that an array is sorted.

        public static void main(String[] args) {
      // int[] nums = {11, 3, 5, 4, 9, 15, 19, 7};
      int[] nums = {3, 2, 4, 1, 6};
      heapSort(nums);

      IntStream.of(nums).forEach(value -> System.out.print(value + ", "));
  }

  /**
  * Ensure that the node's value at i index is greater than the left node and right node's values.
  *
  * Use recursion for its children nodes.
  *
  * @param nums
  * @param i
  */
  public static void heapify(int[] nums, int size, int i) {
      int left = 2 * (i + 1) - 1;
      int right = 2 * (i + 1);
      int largest = -1;

      largest = (left < size) && (nums[i] < nums[left]) ? left : i;
      largest = (right < size) && (nums[largest] < nums[right]) ? right : largest;

      // the children nodes are not satisfied this property
      if (largest != i) {
          // swap the nodes's value at the i and largest index
          int tmp = nums[i];
          nums[i] = nums[largest];
          nums[largest] = tmp;

          heapify(nums, size, largest);
      }
  }

  public static void buildHeap(int[] nums) {
      int middleIdx = (nums.length / 2) - 1;

      for (int i = middleIdx; i >= 0; --i) {
          heapify(nums, nums.length, i);
      }
  }

  public static void heapSort(int[] nums) {
      buildHeap(nums);

      int tmp;
      for (int i = nums.length - 1; i > 0; --i) {
          // swap the largest value at the first index and the value of last index node
          tmp = nums[0];
          nums[0] = nums[i];
          nums[i] = tmp;

          heapify(nums, i, 0);
      }
  }

      The complexity of Heap sort:

      • Time complexity: O(nLogn)
      • Space complexity: O(1)

    • Iterative version


When to use

  • When we want to extract minmum or maximum elements in online queries.


Benefits and Drawbacks

  1. Benefits

    • It is an in-place sorting algorithm.

  2. Drawbacks

    • In reality, it is rarely used to sort an array because merge sort or quick sort works better than it.

    • It’s not stable sorting.

    • It is not cache friendly.


Applications and Examples

  • Used for job scheduling.
  • Used as priority queue.
  • Systems concerned with security and embedded system such as Linux Kernel uses Heap Sort because of the O(nlog(n)) which reduces the processing time of the system.
  • For finding the order in statistics.
  • Heapsort is widely used in external sort. In other words sorting very large files because it allows you to overlap sorting with I/O and that’s the key to successful external sort algorithms.
  • C++’s std::sort routine generally uses a varation of Quicksort called Introsort, which uses Heapsort to sort the current partition if the Quicksort recursion goes too deep, indicating that a worst case has occurred.


Wrapping up

  • Understanding the basic of heap data structure.


Refer:

https://www.quora.com/Why-is-heap-sort-used