Tag Archives: heapsort pseudocode

Heapsort Program and Complexity (Big-O)


Heapsort is a sorting algorithm based on a Binary Heap data structure. It’s a comparison-based sorting similar to Selection Sort where first find maximum item and place that maximum item at the end. Repeat the same steps for remaining items until all items sorted.

Points to Remember

  • Data structure: Array
  • Worst-case performance: O(n\log n)
  • Best-case performance : O(n\log n) (distinct keys) O(n) (equal keys)
  • Average performance: O(n\log n)
  • Worst-case space complexity: O(n) total O(1) auxiliary

See Also: Data Structure and Algorithms Complexity (Big-O)

Advantage

  • Heapsort is a more favorable in worst-case O(n log n) runtime.

Disadvantage

  • Heapsort slower in practice on most machines than a well-implemented quicksort.
  • Heapsort is not a stable sort but in-place algorithm.

Binary Heap Data Structure

Binary Heap is a type of Complete Binary Tree where items stored such a way like a parent node value is greater than the values of its child nodes. That is also called as Max heap. it can be represented in the form of a binary tree or array.

Binary Tree Representation in Array

To represent binary tree structure in the array, consider each array index as a node, where these index of nodes for a parent, left the child and right child follow these expression. In Binary tree for zero-based array ,the root node is stored at index 0; if i is the index of the current node, then

  • parent(i) = floor((i-1) / 2) , where floor map a real number to the smallest leading integer.
  • LeftChild(i) = 2*i + 1
  • RightChild(i) = 2*i + 2

Steps for Heap Sort

  1. Call the heapify() function on the array to make as Max Heap Binary Tree array where Maximum item on the first position.
  2. Swap the first item of the array with the final item. Consider the size of the array by decrease one. Call heapify() on the root of a binary tree.
  3. Repeat the above steps until the size of the unsorted heap is 1.

Note: The heapify() operation is run once, and is O(n) in performance. The swapping() function is O(log n) and is called n times. Therefore, the total performance of this heap sort algorithm is O(n + n log n) = O(n log n).

<h2>Heapsort Java Program</h2>
public class HeapSort {

 public static void main(String []args)
 {
	int[] items = { 2, 6, 3, 8, 4, 1, 5, 0 };
        System.out.println("Before Heap Sorting :");
        printArray(items);

        //Perform heap sort
        heapsort(items);

        System.out.println("After Heap Sorting :");
        printArray(items);
 }

 public static void heapsort(int items[])
 {
     int itemCount = items.length; 

     // Build heap (rearrange array)
     for (int i = itemCount / 2 - 1; i &gt;= 0; i--)
         heapify(items, itemCount, i); 

     // One by one extract an element from heap
     for (int i=itemCount-1; i&gt;=0; i--)
     {
         // Move max root item to end
         int temp = items[0];
         items[0] = items[i];
         items[i] = temp; 

         // call max heapify on the reduced heap
         heapify(items, i, 0);
     }
 } 

 /**
  * Call the heapify() function on the array of decrease size to make as Max Heap Binary
  * Tree array where Maximum item on first position or root.
  */
 static void heapify(int items[], int itemCount, int i)
 {
     int largest = i; // Initialize largest as root
     int l = 2*i + 1; // left = 2*i + 1
     int r = 2*i + 2; // right = 2*i + 2 

     // If left child is larger than root
     if (l  items[largest])
         largest = l; 

     // If right child is larger than largest so far
     if (r  items[largest])
         largest = r; 

     // If largest is not root
     if (largest != i)
     {
         int swap = items[i];
         items[i] = items[largest];
         items[largest] = swap; 

         // Recursively heapify the affected sub tree
         heapify(items, itemCount, largest);
     }
 } 

 static void printArray(int items[])
	{
     for (int item:items)
     {
         System.out.print(item + " ");
     }
     System.out.println();
	}
}

Output


Before Heap Sorting :
2 6 3 8 4 1 5 0 
After Heap Sorting :
0 1 2 3 4 5 6 8