Heapsort

Heapsort is the one of the most efficient comparison-based algorithms with the asymptotic complexity $O(n \\cdot \\log{n})$ . Complexity of heapsort is guaranteed, hence it is fitting to use this algorithm in real time systems instead of quicksort, which is in average case faster, but its worst case complexity is $O(n^{2})$ .

Description

Heapsort is based on usage of the binary heap – data structure which acts as a priority queue. If we insert all elements of the array into the priority queue, the operation poll will always return (and remove) the element of the heap, which has the highest priority. If we use poll operation times, we will obtain list of sorted elements.

The heapsort algorithm consists of these steps:

Build the heap using all elements of the array.
Poll the highest element of the heap.
Swap it with the last element of the heap (in array).
Reduce the heap size by 1 (elements at the end of the heap are already sorted).
Repair the heap (move element swapped in 3 to its correct place in the structure).
If there are any elements remaining in the heap GOTO: 2.
Array is sorted according to the priority of the elements in reverse order.

Heapsort - visualization

Code

     /**
      * Heapsort 
      * @param array array to be sorted
      * @param descending true if the array should be sorted in ascending order, false descending order
      */
     public static void heapSort(Comparable[] array, boolean descending) {
         for (int i = array.length / 2 - 1; i >= 0; i--) {
             repairTop(array, array.length - 1, i, descending ? 1 : -1);
         }
         for (int i = array.length - 1; i > 0; i--) {
             swap(array, 0, i);
             repairTop(array, i - 1, 0, descending ? 1 : -1);
         }
     }
 
     /**
      * Move the top of the heap to the correct place
      * @param array array to be sorted
      * @param bottom last index that can be touched
      * @param topIndex index of the top of the heap
      * @param order 1 == descending order, -1 ascending order
      */
     private static void repairTop(Comparable[] array, int bottom, int topIndex, int order) {
         Comparable tmp = array[topIndex];
         int succ = topIndex * 2 + 1;
         if (succ < bottom && array[succ].compareTo(array[succ + 1]) == order) {
             succ++;
         }
 
         while (succ <= bottom && tmp.compareTo(array[succ]) == order) {
             array[topIndex] = array[succ];
             topIndex = succ;
             succ = succ * 2 + 1;
             if (succ < bottom && array[succ].compareTo(array[succ + 1]) == order) {
                 succ++;
             }
         }
         array[topIndex] = tmp;
     }
 
     /**
      * Swaps two elements of the heap
      * @param array array
      * @param left index of the first element
      * @param right index of the second element
      */
     private static void swap(Comparable[] array, int left, int right) {
         Comparable tmp = array[right];
         array[right] = array[left];
         array[left] = tmp;
     }

 /**
  * Heapsort (descending)
  * @param array array to be sorted
  * @param size size of the array
  */
 void heapsort(int array[], int size) {
     for (int i = size/2 - 1; i >= 0; i--) {
         repairTop(array, size - 1, i);
     }
     for (int i = size - 1; i > 0; i--) {
         swap(array, 0, i);
         repairTop(array, i - 1, 0);
     }
 }
 
 /**
  * Move the top of the heap to the correct place
  * @param array array to be sorted
  * @param bottom last index that can be touched
  * @param topIndex index of the top of the heap
  */
 void repairTop(int array[], int bottom, int topIndex) {
     int tmp = array[topIndex];
     int succ = topIndex*2 + 1;
     if (succ < bottom && array[succ] > array[succ+1]) succ++;
     
     while (succ <= bottom && tmp > array[succ]) {
         array[topIndex] = array[succ];
         topIndex = succ;
         succ = succ*2 + 1;
         if (succ < bottom && array[succ] > array[succ+1]) succ++;
     }
     array[topIndex] = tmp; 
 }
 
 /**
  * Swaps two elements of the heap
  * @param array array
  * @param left index of the first element
  * @param right index of the second element
  */
 void swap(int array[], int left, int right) {
     int tmp = array[right]; 
     array[right] = array[left];
     array[left] = tmp;         
 }

        /**
         * Heapsort 
         * @param array array to be sorted
         * @param ascending @true if the array should be sorted in ascending order, @false descending order
         */
         public static void Heapsort(int[] array)
         {
             for (int i = array.Length / 2 - 1; i >= 0; i--)
             {
                 RepairTop(array, array.Length - 1, i);
             }
             for (int i = array.Length - 1; i > 0; i--)
             {
                 Swap(array, 0, i);
                 RepairTop(array, i - 1, 0);
             }
         }
 
        /**
         * Move the top of the heap to the correct place
         * @param array array to be sorted
         * @param bottom last index that can be touched
         * @param topIndex index of the top of the heap
         * @param order 1 == ascending order, -1 descending order
         */
         private static void RepairTop(int[] array, int bottom, int topIndex)
         {
             int tmp = array[topIndex];
             int succ = topIndex * 2 + 1;
             if (succ < bottom && array[succ] > array[succ + 1]) succ++;
 
             while (succ <= bottom && tmp > array[succ])
             {
                 array[topIndex] = array[succ];
                 topIndex = succ;
                 succ = succ * 2 + 1;
                 if (succ < bottom && array[succ] > array[succ + 1]) succ++;
             }
             array[topIndex] = tmp;
         }
 
        /**
         * Swaps two elements of the heap
         * @param array array
         * @param left index of the first element
         * @param right index of the second element
         */
         private static void Swap(int[] array, int left, int right)
         {
             int tmp = array[right];
             array[right] = array[left];
             array[left] = tmp;
         }

Analysis

Binary heap
(the lower value has a higher priority)

Heap

A Heap is a binary tree with the recursive property of being a heap. The recursivity means that every subtree of a heap is a heap too. In every heap ancestor node has a higher priority than both of its children. If is the heap implemented using array and index of the parent node is i, than the children are located at indexes 2i +1 and 2i+1 (where the first element of the array has index 0). The consequence of this ordering is the shape of the heap – pyramid with chopped off right part of its base.

Repair top

The repair top procedure restores the inner structure of the heap – ordering of the elements when we know that the head of the heap is incorrectly positioned. In every step it compares the parent element with both of its children and if the parent has a lower priority than one of its children, than the procedure swaps it with the child with higher priority. Since this action could only caused transmission of the disbalance one level lower, repair top procedure repeats this step iteratively at all levels. The procedure terminates when all levels are repaired, or when the being a heap property is restored (parent has a higher priority than both of its children).

Heapsort

As we have already mentioned being a heap is a recursive property, hence at first we have to repair all subheaps from smallest to largest. Because descendants of all elements are located at indexes 2i+1 and 2i+2 , we know that the first head of a non-trivial heap must be located at index array.length/2 -1 .

After we repair all subheaps and the heap itself, we can sort the array using iterative procedure described above (poll, swap with the last element, reduce the size of the heap, repair the heap).

Place for your banner

Here is the position ready for our customer's banners.