A heap can be seen as a complete binary tree. You can think of unfilled (black nodes as given in image below) slots as null pointers.Heaps also satisfy the heap property:

A[Parent(i)] > A[i] for all nodes i > 1

Heaps can also be represented as an array. To represent a complete binary tree as an array:

  • The root node is A[1]
  • Node i is A[i]
  • The parent of node i is A[i/2] (note: integer divide)
  • The left child of node i is A[2i]
  • The right child of node i is A[2i + 1]

The value of a node is at most the value of its parent. The height of a node in the tree is equal to the number of edges on the longest downward path to a leaf.

How Heap sort works?

Heap sort algorithm works in two phases. In first phase, a heap is built. Building a heap uses Heapify on every node. In second phase, Heap sort algorithm takes largest element off the heap and places it at the end of an array. This phase continue until all the elements are placed in the array that are in sorted order.

Heapify function

Heapify() function maintain the heap property

Given: a node i in the heap with children l and r

Given: two subtrees rooted at l and r, assumed to be heaps

Problem: The subtree rooted at i may violate the heap property

Action: let the value of the parent node “float down” so subtree at i satisfies the heap property.

Heapify(A, i)
	l = Left(i); r = Right(i);
	if (l <= heap_size(A) && A[l] > A[i])
		largest = l;
		largest = i;
	if (r <= heap_size(A) && A[r] > A[largest])
		largest = r;
	if (largest != i)
		Swap(A, i, largest);
		Heapify(A, largest);

BuildHeap function

We can build a heap in a bottom-up manner by running Heapify() on successive sub-arrays. This algorithm will iterate through each node and then run Heapify() on it.

// given an unsorted array A, make A a heap
	heap_size(A) = length(A);
	for (i = ëlength[A]/2û  downto 1)
		Heapify(A, i);

Heapsort function 

Finally, both BuildHeap and Heapify can be used in within Heapsort algorithm to sort an array.

		for (i = length(A) downto 2)
			Swap(A[1], A[i]);
			heap_size(A) -= 1;
			Heapify(A, 1);

Graphical Explanation of Heap sort



Tagged with: C/C++ language

One Response to Heap Sort with Graphical Explanation

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>


Looking for something?

Use the form below to search the site:

Still not finding what you're looking for? Drop a comment on a post or contact us so we can take care of it!

Related News Feeds

Set your Twitter account name in your settings to use the TwitterBar Section.