Heap Structure

Heaps
• A binary heap is a binary tree (NOT a BST) that is:
• Complete: the tree is completely filled except possibly the bottom
level, which is filled from left to right
• Satisfies the heap order property
• The ordering can be one of two types:
• min-heap property: the value of each node is greater than or equal
to the value of its parent, with the minimum-value element at the
root.
• max-heap property: the value of each node is less than or equal to
the value of its parent, with the maximum-value element at the root.
Example

Min Heap Max Heap

Heap Properties
Structure property: A heap is a completely filled binary tree with the
exception of the bottom row, which is filled from left to right
Heap Order property: For every node x in the heap, the parent of x
greater than or equal to the value of x.
(known as a maxHeap).
Heaps
• Points to note:
• There is no restriction on the ordering of the children of a node.
• No tree traversal will output the items in sorted order.
Heap or not
Heaps (or not)?
9
9

5 7
5 7
6 2 1
4 2 5

tree 1 tree 2

5 7

2 1

tree 3
Binary heap vs Binary search tree
Consider the figure given below and state whether
it is a heap or not.
Array representation of heap
• Since a heap is defined as a complete binary tree, all its elements can
be stored sequentially in an array.
• It follows the same rules of complete binary tree.
• That is, if an element at position i in the array, has its left child stored
at position 2i and its right child at position 2i + 1.
• Conversely, an element at position i have its position stored at
position i/2.
Simplifying things
• Place the root at array index 1, its left child at index 2, its right child at index
3, so on and so forth…

53

44 25

15 21 13 18

3 12 5 7

53 44 25 15 21 13 18 3 12 5 7

0 1 2 3 4 5 6 7 8 9 10 11
 53

44 25

15 21 13 18

3 12 5 7

53 44 25 15 21 13 18 3 12 5 7

0 1 2 3 4 5 6 7 8 9 10 11

For any node i, the following formulas apply:

The index of its parent = i / 2
Index of left child = 2 * i
Index of right child = 2 * i + 1
Operations on Heaps
• Maintain/Restore the max-heap property
• MAX-HEAPIFY

• Create a max-heap from an unordered array

• BUILD-MAX-HEAP

• Sort an array in place

• HEAPSORT

• Priority queues

13
Building a Heap
• Convert an array A[1 … n] into a max-heap (n = length[A])
• The elements in the subarray A[(n/2+1) .. n] are leaves
• Apply MAX-HEAPIFY on elements between 1 and n/2

Alg: BUILD-MAX-HEAP(A) 1

4
1. n = length[A]
2 3
2. for i ← n/2 downto 1 1 3
4 5 6 7

3. do MAX-HEAPIFY(A, i, n) 8
2 9 10
16 9 10
14 8 7

A: 4 1 3 2 16 9 10 14 8 7

14
Example: A 4 1 3 2 16 9 10 14 8 7

i=5 i=4 i=3

1 1 1

4 4 4
2 3 2 3 2 3

1 3 1 3 1 3
4 5 6 7 4 5 6 7 4 5 6 7

8
2 9 10
16 9 10 8 2 9 10
16 9 10 8 14 9 10
16 9 10
14 8 7 14 8 7 2 8 7

i=2 i=1
1 1 1

4 4 16
2 3 2 3 2 3

1 10 16 10 14 10
4 5 6 7 4 5 6 7 4 5 6 7

8
14 9 10
16 9 3 8
14 9 10
7 9 3 8
8 9 10
7 9 3
2 8 7 2 8 1 2 4 1
15
Maintaining the Heap Property
• Suppose a node is smaller than a child
• Left and Right subtrees of i are max-heaps
• To eliminate the violation:
• Exchange with larger child
• Move down the tree
• Continue until node is not smaller than
children

16
Example
MAX-HEAPIFY(A, 2, 10)

A[2]  A[4]

A[2] violates the heap property A[4] violates the heap property

A[4]  A[9]

Heap property restored

17
Build a max heap H from the given set of
numbers : 45, 36, 54, 27, 63, 72, 61 and 18
• Also draw the memory representation of the heap
 Build a max heap H from the given set of numbers : 45, 36, 54,
27, 63, 72, 61 and 18
Also draw the memory representation of the heap
 Build a max heap H from the given set of numbers : 45, 36, 54,
27, 63, 72, 61 and 18
Also draw the memory representation of the heap
Form a binary max-heap and a min-heap from the
following sequence of data:
50, 40, 35, 25, 20, 27, 33.
Form a binary max-heap from the following
sequence of data:
2,60, 70,23,12,16, 85,22,43,7
Which of the following sequences represents
a binary heap?
( c)40, 33, 35, 22, 12, 16, 5, 7
(b) 44, 37, 20, 22, 16, 32, 12
(c) 15, 15, 15, 15, 15, 15
 Maintaining the Heap Property
• Assumptions:
• Left and Right subtrees of i are Alg: MAX-HEAPIFY(A, i, n)
max-heaps
• A[i] may be smaller than its 1. l ← LEFT(i)
children
2. r ← RIGHT(i)
3. if l ≤ n and A[l] > A[i]
Alg: BUILD-MAX-HEAP(A)
4. then largest ←l
1. n = length[A]
5. else largest ←i
2. for i ← n/2 downto 1
6. if r ≤ n and A[r] > A[largest]
3. do MAX-HEAPIFY(A, i, n)
7. then largest ←r
[1] [2] [3] [4] [5] [6]
8. if largest  i
4 14 7 2 8 1 9. then exchange A[i] ↔ A[largest]
10. MAX-HEAPIFY(A, largest, n)

24
Heapsort
• Goal:
• Sort an array using heap representations

• Idea:
• Build a max-heap from the array
• Swap the root (the maximum element) with the last
element in the array
• “Discard” this last node by decreasing the heap size
• Call MAX-HEAPIFY on the new root
• Repeat this process until only one node remains

25
Example: A=[7, 4, 3, 1, 2]

MAX-HEAPIFY(A, 1, 4) MAX-HEAPIFY(A, 1, 3) MAX-HEAPIFY(A, 1, 2)

MAX-HEAPIFY(A, 1, 1)

26
Alg: HEAPSORT(A)
1. BUILD-MAX-HEAP(A)
2. for i ← length[A] downto 2
3. do exchange A[1] ↔ A[i]
4. MAX-HEAPIFY(A, 1, i - 1)

27
Problems
• Demonstrate, step by step, the operation of Build-Heap on the array
and perform sorting using heapsort
A=[5, 3, 17, 10, 84, 19, 6, 22, 9]

28