1 of 29

Lecture 11:�Priority Queue & Heap

2 of 29

Announcement & Tentative Schedule

10/30 - Quiz 2
11/3 - 11/14: Priority Queue, Heap
11/17 - Quiz 3
11/20-12/4 : Hash Table, Graph
12/8: Quiz 4

2

3 of 29

Queue: Recap

Queue: �First In First Out (FIFO)�

Adding a new element (enqueue)
Retrieving the oldest item (peek)
Deleting an item (dequeue)

3

enqueue

15

22

dequeue

11

9

3

4 of 29

Priority Queue

Each element consists of {key (priority), value (element)}

Enqueue: Any order
Dequeue: Delete by priority

Example: Airplane boarding group

4

5 of 29

Priority Queue

Ordered Queue (for faster deletion)

Enqueue: O(n)
Dequeue: O(1)

Key

Value

5

6 of 29

Priority Queue

Unordered Queue (for faster insertion)

Enqueue: O(1)
Dequeue: O(n)

Can we implement enqueue and dequeue in O(log(n))?

Key

Value

6

7 of 29

Heap

7

8 of 29

(Recap: Tree) Complete Binary Tree

Def. A binary tree T is called Complete binary tree, if

T is full down to level h - 1, and
with level h filled in from left to right.

Complete BT of

Height 2

Complete BT of

Height 3

Complete BT of Height 4

Must be filled (to be complete)

Optionally filled (to be complete)

8

9 of 29

(Recap: Tree) Array-based Implementation

One more thing to consider: How can we figure out direct children of a node?

With a tree, we usually access data from the root to the leaf.
Common rule connecting a node to its children?

From parent, its left child:�[parent index] * 2 + 1 😀
Right child:�[parent index] * 2 + 2 😄

Similarly, from a child, its parent:�[child index - 1] // 2

[1]

[2]

[3]

[4]

[5]

[6]

[0]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

8

7

2

3

9

2

1

5

9

10 of 29

Binary Heap

Min Heap

Max Heap

Heap-Order: key(v) ≥ key(parent(v))�
Complete Binary Tree

10

11 of 29

Heap and Priority Queue

We can use a heap to implement a priority queue
We store a (key, element) item at each internal node
We keep track of the position of the last node
For simplicity, we show only the keys in the picture

11

12 of 29

Insertion

Insertion of a key (priority) k to the heap
The insertion algorithm consists of 2 steps

Store k at the new last node
Restore the heap-order property �(heapify_up: next slide)

12

13 of 29

Heapify-up

After the insertion of a new key k, the heap-order property may be violated
Algorithm heapify-up restores the heap-order property by swapping k along an upward path from the insertion node
Heapify-up terminates when the key k reaches the root or a node whose parent has a key smaller than or equal to k
Since a heap has height O(log n), heapify-up runs in O(log n) time

13

14 of 29

Insertion example

left child:�[parent index] * 2 + 1
Right child:�[parent index] * 2 + 2
parent:�[child index - 1] // 2

14

15 of 29

Insertion example

left child:�[parent index] * 2 + 1
Right child:�[parent index] * 2 + 2
parent:�[child index - 1] // 2

15

16 of 29

Insertion example

left child:�[parent index] * 2 + 1
Right child:�[parent index] * 2 + 2
parent:�[child index - 1] // 2

16

17 of 29

Insertion example

left child:�[parent index] * 2 + 1
Right child:�[parent index] * 2 + 2
parent:�[child index - 1] // 2

17

18 of 29

Insertion example

left child:�[parent index] * 2 + 1
Right child:�[parent index] * 2 + 2
parent:�[child index - 1] // 2

18

19 of 29

Insertion example

left child:�[parent index] * 2 + 1
Right child:�[parent index] * 2 + 2
parent:�[child index - 1] // 2

19

20 of 29

Insertion example

left child:�[parent index] * 2 + 1
Right child:�[parent index] * 2 + 2
parent:�[child index - 1] // 2

20

21 of 29

Deletion

Removal of the root key (highest priority) from the heap
The removal algorithm consists of 2 steps

Replace the root key with the key �of the last node.
Restore the heap-order property �(Heapify-down: next)

21

22 of 29

Heapify-down

After replacing the root key with the key k of the last node, the heap-order property may be violated
Algorithm heapify-down restores the heap property by swapping key k with the child with the smallest key along a downward path from the root
Heapify-down terminates when key k reaches a leaf or a node whose children have keys greater than or equal to k
Since a heap has height O(log n), heapify-down runs in O(log n) time

22

23 of 29

Deletion Example

left child:�[parent index] * 2 + 1
Right child:�[parent index] * 2 + 2
parent:�[child index - 1] // 2

Deletion in Max(or Min) Heap always�happens at the root to remove Maximum (or Minimum) value
Deleting it (or removing it) from root cause a hole which needs to be filled.

23

24 of 29

Deletion Example

left child:�[parent index] * 2 + 1
Right child:�[parent index] * 2 + 2
parent:�[child index - 1] // 2

31

24

25 of 29

Deletion Example

left child:�[parent index] * 2 + 1
Right child:�[parent index] * 2 + 2
parent:�[child index - 1] // 2

31

25

26 of 29

Deletion Example

left child:�[parent index] * 2 + 1
Right child:�[parent index] * 2 + 2
parent:�[child index - 1] // 2

26

27 of 29

Implementation (array)

27

28 of 29

Implementation (array)

28

29 of 29

Heap-sort (Min heap)

O(n log n) Sorting!

	Insert	Remove�Min	PQ-Sort Total
Heap Sort	O(logn)	O(logn)	O(n logn)

29