Heap Sort

Posted By on September 18, 2014


Download PDF
Activity selection problem
Quick Sort

Heapsort is a comparison-based sorting algorithm. Heapsort is part of the selection sort family; it improves on the basic selection sort by using a logarithmic-time priority queue rather than a linear-time search. Although somewhat slower in practice on most machines than a well-implemented quicksort, it has the advantage of a more favorable worst-case O(n log n) runtime. Heapsort is an in-place algorithm, but it is not a stable sort. It was invented by J. W. J. Williams in 1964.

Heapsort
Sorting heapsort anim.gif

A run of the heapsort algorithm sorting an array of randomly permuted values. In the first stage of the algorithm the array elements are reordered to satisfy the heap property. Before the actual sorting takes place, the heap tree structure is shown briefly for illustration.
Class Sorting algorithm
Data structure Array
Worst case performance O(nlog n)
Best case performance Omega(n), O(nlog n)[1]
Average case performance O(nlog n)
Worst case space complexity O(1) auxiliary

The heapsort algorithm can be divided into two parts.

In the first step, a heap is built out of the data. The heap is often placed in an array with the layout of a complete binary tree. The complete binary tree maps the binary tree structure into the array indices; each array index represents a node; the index of the node’s parent, left child branch, or right child branch are simple expressions. For a zero-based array, the root node is stored at index 0; if i is the index of the current node, then

  iParent     = floor((i-1) / 2)
  iLeftChild  = 2*i + 1
  iRightChild = 2*i + 2

In the second step, a sorted array is created by repeatedly removing the largest element from the heap (the root of the heap), and inserting it into the array. The heap is updated after each removal to maintain the heap. Once all objects have been removed from the heap, the result is a sorted array.

Heapsort can be performed in place. The array can be split into two parts, the sorted array and the heap. The storage of heaps as arrays is diagrammed here. The heap’s invariant is preserved after each extraction, so the only cost is that of extraction.

Example

Let { 6, 5, 3, 1, 8, 7, 2, 4 } be the list that we want to sort from the smallest to the largest. (NOTE, for ‘Building the Heap’ step: Larger nodes don’t stay below smaller node parents. They are swapped with parents, and then recursively checked if another swap is needed, to keep larger numbers above smaller numbers on the heap binary tree.)

An example on heapsort.

1. Build the heap

Heap newly added element swap elements
nil 6
6 5
6, 5 3
6, 5, 3 1
6, 5, 3, 1 8
6, 5, 3, 1, 8 5, 8
6, 8, 3, 1, 5 6, 8
8, 6, 3, 1, 5 7
8, 6, 3, 1, 5, 7 3, 7
8, 6, 7, 1, 5, 3 2
8, 6, 7, 1, 5, 3, 2 4
8, 6, 7, 1, 5, 3, 2, 4 1, 4
8, 6, 7, 4, 5, 3, 2, 1

2. Sorting.

Heap swap elements delete element sorted array details
8, 6, 7, 4, 5, 3, 2, 1 8, 1 swap 8 and 1 in order to delete 8 from heap
1, 6, 7, 4, 5, 3, 2, 8 8 delete 8 from heap and add to sorted array
1, 6, 7, 4, 5, 3, 2 1, 7 8 swap 1 and 7 as they are not in order in the heap
7, 6, 1, 4, 5, 3, 2 1, 3 8 swap 1 and 3 as they are not in order in the heap
7, 6, 3, 4, 5, 1, 2 7, 2 8 swap 7 and 2 in order to delete 7 from heap
2, 6, 3, 4, 5, 1, 7 7 8 delete 7 from heap and add to sorted array
2, 6, 3, 4, 5, 1 2, 6 7, 8 swap 2 and 6 as they are not in order in the heap
6, 2, 3, 4, 5, 1 2, 5 7, 8 swap 2 and 5 as they are not in order in the heap
6, 5, 3, 4, 2, 1 6, 1 7, 8 swap 6 and 1 in order to delete 6 from heap
1, 5, 3, 4, 2, 6 6 7, 8 delete 6 from heap and add to sorted array
1, 5, 3, 4, 2 1, 5 6, 7, 8 swap 1 and 5 as they are not in order in the heap
5, 1, 3, 4, 2 1, 4 6, 7, 8 swap 1 and 4 as they are not in order in the heap
5, 4, 3, 1, 2 5, 2 6, 7, 8 swap 5 and 2 in order to delete 5 from heap
2, 4, 3, 1, 5 5 6, 7, 8 delete 5 from heap and add to sorted array
2, 4, 3, 1 2, 4 5, 6, 7, 8 swap 2 and 4 as they are not in order in the heap
4, 2, 3, 1 4, 1 5, 6, 7, 8 swap 4 and 1 in order to delete 4 from heap
1, 2, 3, 4 4 5, 6, 7, 8 delete 4 from heap and add to sorted array
1, 2, 3 1, 3 4, 5, 6, 7, 8 swap 1 and 3 as they are not in order in the heap
3, 2, 1 3, 1 4, 5, 6, 7, 8 swap 3 and 1 in order to delete 3 from heap
1, 2, 3 3 4, 5, 6, 7, 8 delete 3 from heap and add to sorted array
1, 2 1, 2 3, 4, 5, 6, 7, 8 swap 1 and 2 as they are not in order in the heap
2, 1 2, 1 3, 4, 5, 6, 7, 8 swap 2 and 1 in order to delete 2 from heap
1, 2 2 3, 4, 5, 6, 7, 8 delete 2 from heap and add to sorted array
1 1 2, 3, 4, 5, 6, 7, 8 delete 1 from heap and add to sorted array
1, 2, 3, 4, 5, 6, 7, 8 completed
Activity selection problem
Quick Sort

Download PDF

Posted by Akash Kurup

Founder and C.E.O, World4Engineers Educationist and Entrepreneur by passion. Orator and blogger by hobby

Website: http://world4engineers.com