Data Structures

Fall 2023

18. Heap Sort

 Binary Heap

Data Structures 19 - Heap Sort 2

Recall: Priority Queue

4
10
19
5 3
13 8
11 22
insert()

deleteMin()

3 Dequeues the next element

with the highest priority

Data Structures 18 - Heap Sort 3

Recall: Priority Queue

• Unordered linked list

– Insert – O(1) step 5 2 10 … 3
– deleteMin – O(n) steps

• Ordered linked list

– insert – O(n) steps 2 3 5 … 10
– deleteMin – O(1) step

Can we build a data structure better suited

to store and retrieve priorities?

Data Structures 18 - Heap Sort 4

Binary Heap

• A binary heap is a binary tree with two properties

– Structure property
– Heap-order property

Data Structures 18 - Heap Sort 5

Binary Heap – Structure Property

• A binary heap is (almost) complete binary tree

– Each level (except possibly the bottom most level) is completely filled
– The bottom most level may be partially filled (from left to right)

N=10

Every level
(except last)
saturated

Data Structures 18 - Heap Sort 6

Binary Heap – Heap-Order Property

• Min-Heap property
– Key associated with the root is less than or equal to the keys
associated with either of the sub-trees (if any)
– Both of the sub-trees (if any) are also binary min-heaps

• Properties of min-heap
– A single node is a min-heap
– Minimum key always at root
– For every node X, key(parent(X)) ≤ key(X)
– No relationship between nodes with similar key

Data Structures 18 - Heap Sort 7

Heap-Order Property – Example

• Min-Heap

Minimum
  element

   

   

No relationship

Data Structures 18 - Heap Sort 8

Binary Heap – Heap-Order Property

• Max-Heap property
– Maximum key at the root
– For every node X, key(parent(X)) ≥ key(X)

• Insert and deleteMin must maintain heap-order property

Data Structures 18 - Heap Sort 9

Heap Operations – insert

• Insert new element into the heap at the next available slot (“hole”)
– Maintaining (almost) complete binary tree
• Percolate the element up the heap while heap-order property not
satisfied

Data Structures 18 - Heap Sort 10

Heap Insert – Example

• Insert 14

14 hole

Data Structures 18 - Heap Sort 11

Heap Insert – Example

• Insert 14

(1)
14 vs. 31

14

14 hole

Data Structures 18 - Heap Sort 12

Heap Insert – Example

• Insert 14

(2)
14 vs. 21 14

14

Data Structures 18 - Heap Sort 13

Heap Insert – Example

• Insert 14

(3)
14 vs. 13
14

Path of percolating up

Heap order property

Structure property

Data Structures 18 - Heap Sort 14

Heap Operation – deleteMin

• Minimum element is always at the root

– Return the element at the root
• Copy value of last element of the tree into hole at root and delete
last node
• Heapify: Percolate down until heap-order property not satisfied

Replace 13
with 31 here

Move 31 down

Delete this
node
Data Structures 18 - Heap Sort 15
deleteMin – Example

Copy 31 temporarily
here and move it down

Make this
position Is 31 > min(14,16)?
empty - Yes - swap 31 with min(14,16)

Data Structures 18 - Heap Sort 16

deleteMin – Example

31

Is 31 > min(19,21)?
- Yes - swap 31 with min(19,21)

Data Structures 18 - Heap Sort 17

deleteMin – Example

31

31

Is 31 > min(19,21)? Is 31 > min(65,26)?

- Yes - swap 31 with min(19,21) - Yes - swap 31 with min(65,26)

Data Structures 18 - Heap Sort 18

deleteMin – Example

31

Data Structures 18 - Heap Sort 19

Runtime Analysis
• insert operation
– Worst case: Inserting an element less than the root
 O(log2 n)
– Best case: Inserting an element greater than any other element
 O(1)
– Average case: O(1)
 Why ?

• deleteMin operation
– Replacing the top element is O(1)
– Percolate down the top object is O(log2 n)
– We copy something that is already in the lowest depth
 It will likely be moved back to the lowest depth

Data Structures 18 - Heap Sort 20

Array-Based Implementation Of Binary Tree

Left child(i) = at position 2i

N=10 Right child(i) = at position 2i + 1
Parent(i) = at position i / 2

Array representation:

i
2i + 1

i / 2 2i
Data Structures 18 - Heap Sort 21
Array-Based Implementation Of Binary Heap

• Consider the following heap, both as a tree and in its array

representation

Data Structures 18 - Heap Sort 22

Array-Based Implementation – insert

• Inserting 26 requires no changes

i / 2

Data Structures 18 - Heap Sort 23

Array-Based Implementation – insert

• Inserting 8 requires a few percolations

– Swap 8 and 23

i / 2
Data Structures 18 - Heap Sort 24
Array-Based Implementation – insert

• Swap 8 and 12

Data Structures 18 - Heap Sort 25

Array-Based Implementation – insert

• At this point, 8 is greater than its parent, so we are finished

Data Structures 18 - Heap Sort 26

Array-Based Implementation – deleteMin

• Removing the top require copy of the last element to the top

Data Structures 18 - Heap Sort 27

Array-Based Implementation – deleteMin

• Heapify: Percolate down

– Compare Node 1 with its children: Nodes 2 and 3
– Swap 23 and 6
Left child(i) = at position 2i
Right child(i) = at position 2i + 1

Data Structures 18 - Heap Sort 28

Array-Based Implementation – deleteMin

• Compare Node 2 with its children: Nodes 4 and 5

– Swap 23 and 9
Left child(i) = at position 2i
Right child(i) = at position 2i + 1

Data Structures 18 - Heap Sort 29

Array-Based Implementation – deleteMin

• Compare Node 4 with its children: Nodes 8 and 9

– Swap 23 and 10

Left child(i) = at position 2i

Right child(i) = at position 2i + 1

Data Structures 18 - Heap Sort 30

Array-Based Implementation – deleteMin

• The children of Node 8 are beyond the end of the array:

– Stop
Left child(i) = at position 2i
Right child(i) = at position 2i + 1

Data Structures 18 - Heap Sort 31

Building a Heap

• What if all N elements are all available upfront?

– Construct heap from initial set of N items

• Solution 1 (insert method)

– Perform N inserts

• Solution 2 (BuildHeap method)

– Randomly populate initial heap with structure property
– Perform a heapify/percolate-down operation from each internal node
 To take care of heap order property

Data Structures 18 - Heap Sort 32

BuildHeap Example

• Input priority levels

– { 150, 80, 40, 30, 10, 70, 110, 100, 20, 90, 60, 50, 120, 140, 130 }

Leaves are all

valid heaps
(implicitly)

• Arbitrarily assign elements to heap nodes So, let us look at each

internal node,
• Structure property satisfied
from bottom to top,
• Heap order property violated
and fix if necessary
• Leaves are all valid heaps (implicit)
Data Structures 18 - Heap Sort 33
BuildHeap Example

Nothing
to do

Data Structures 18 - Heap Sort 34

BuildHeap Example

Swap with
left child

Data Structures 18 - Heap Sort 35

BuildHeap Example

Nothing
to do

Data Structures 18 - Heap Sort 36

BuildHeap Example

Swap
with right
child

Data Structures 18 - Heap Sort 37

BuildHeap Example

Nothing
to do

Data Structures 18 - Heap Sort 38

BuildHeap Example

Swap with right child

and then with 60

Data Structures 18 - Heap Sort 39

BuildHeap Example

Data Structures 18 - Heap Sort 40

BuildHeap Example

Final Heap

Data Structures 18 - Heap Sort 41

Heap Sort

• Consists of two steps:

– Build Heap
– Delete elements one by one

• Algorithm:
– Build a heap from the given input array
 Heapify all non-leaf nodes
– Repeat the following steps until the heap contains only one element
 Swap the root element of the heap with the last element of the heap
 Remove the last element of the heap
 Heapify the remaining elements of the heap to maintain heap order

• Use max-heap for ascending sort and min-heap for descending sort

Data Structures 18 - Heap Sort 42

Heap Sort

Data Structures 18 - Heap Sort 43

Heap Sort

Data Structures 18 - Heap Sort 44

Any Question So Far?

Data Structures 18 - Heap Sort 45