# Heap Sort with Graphical Explanation

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[2*i*] - The right child of node
*i*is A[2*i*+ 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; else 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 BuildHeap(A) { 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.

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

## Graphical Explanation of Heap sort

### Related Posts

- Introduction to Tree Data Structure
- Binary Search Trees and Data Structure
- Heap data structure in C++
- Binary Expression Trees
- Binary Trees and Binary Search Trees
- This Pointer, Static Members and destructors in C++
- Graph search in C++
- Graphical Path Finding System using Dijkstra Algorithm
- Insertion Sort: A Graphical Explanation
- Operations on Binary Search Trees (BST)
- Merge Sort with Graphical explanation
- Advanced Data Structures Tutorial using C++

### One Response to *Heap Sort with Graphical Explanation*

### Leave a Reply Cancel reply

### Popular Posts (last 30 days)

- Attendance Management Sys… 1203 view(s)
- Implementing Stack Data S… 596 view(s)
- Graph Implementation in C… 594 view(s)
- Applications of Stack in … 536 view(s)
- Circular Linked Lists 526 view(s)
- Simple Currency Converter… 444 view(s)
- GRASP Design Patterns 330 view(s)
- Advanced Data Structures … 268 view(s)
- C++ Tutorial for Intermed… 260 view(s)
- Sockets and Network Progr… 187 view(s)

### Related Links

### Tags

Android C-Sharp C/C++ language Classes Data structures Design Pattern Eclipse Game Development Graphics Design Books HTML iPhone JAVA JAVA GUI MIPS Assembly Mobile Programming Books Object Oriented PDF PHP Programming Programming Books Programming Languages Books Python RaphaelJS REST Source Code Threads Tutorial Web Development Books

Better way to implement Heap Sort