[Algorithms] Heapsort

Heapsort is a kind of in-place sorting algorithm like insertion sort.
Heapsort is also a O(nlgn) algorithm like merge sort.

7 main functions: first 3 used for sorting, last 4 for priority queue.
Note: in the code A[1..n] instead of A[0..n-1].

Max-Heapify:

• Condition: LEFT(i) & RIGHT(i) are both max-heap. A[i] might violates the rule.
• Code:                                                                                                            public void maxHeapify(int[] A, int i) {
      int left = left(i);
      int right = right(i);
      int largest = 0;
      if (l < heapSize && A[left] > A[i]) largest = left;
      else largest = i;
      if (r < heapSize && A[right] > A[largest]) largest = right;
      if (largest == i) {
          exchange A[i] & A[largest];
          maxHeapify(A, largest);
      }
  }
• Time: O(lgn)

Build-Max-Heap:

• Condition: We want to build a max-heap. The fact is A[n/2+1 to n] is all leaves.
• Code:                                                                                                          public void buildMaxHeap(int[] A) {
      heapSize = A.length;
      for (int i = A.length/2; i > 0; i--) maxHeapify(A, i);
  }
• Time: O(nlgn) BUT actually we will have a more tight Time bound O(n). It is because time cost by maxHeapify to different node is not the same. It is  proportional to O(h) where h is the node's height, and most nodes possess a small height.

Heap-Sort:

• Condition: We move the maximum of the heap to the end of the array. And Adjust the heap.
• Code:                                                                                                           public void heapSort(int[] A) {
      buildMaxHeap(A);
      for (int i = A.length; i > 1; i--) {
          exchange A[1] & A[i];
          heapSize--;
          maxHeapify(A, 1);
      }
  }
• Time: O(nlgn)

Max-Heap-Insert:

• Condition: Insert a key into this heap.
• Code:
  public void maxHeapInsert(A, key) {
      heapSize++;
      A[heapSize] = Integer.MIN_VALUE;
      heapIncreaseKey(A, heapSize, key);
  }
• Time: O(lgn)

Heap-Extract-Max:

• Condition: Remove the Maximum from the heap.
• Code:
  public int heapExtractMax(int[] A) {
      max = A[1];
      A[1] = A[heapSize];
      heapSize--;
      maxHeapify(A, 1);
      return max;   
  }
• Time: O(lgn)

Heap-Increase-Key:

• Condition: Increase some key in this heap.
• Code:
  public void heapIncreaseKey(int[] A, int i, int key) {
      A[i] = key;
      while (i > 1 & A[parent(i)] < A[i]) {
          exchange A[i] & A[parent(i)];
          i = parent(i);
      }
  }
• Time: O(lgn)

Heap-Maximum

• Condition: Return the maximum of the heap.
• Code:                                                                                                            public int heapMaximum(int[] A) {
      return A[1];
  }
• Time: O(1)