1 of 40

Lecture 12:�Priority Queue & Heap (Continue)

2 of 40

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 40

Priority Queue

  • Each element consists of {key (priority), value (element)}
    • Enqueue: Any order
    • Dequeue: Delete by priority
  • Example: Airplane boarding group

3

4 of 40

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

4

5 of 40

Priority Queue

  • Ordered Queue (for faster deletion)
    • Enqueue: O(n)
    • Dequeue: O(1)

Key

​

Value

5

6 of 40

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 40

Heap

7

8 of 40

Binary Heap

Min Heap

Max Heap

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

 

8

9 of 40

Max-heap: Insertion

  • Insertion of a key (priority) k to the heap
  • The insertion algorithm consists of 2 steps
    1. Store k at the new last node
    2. Restore the heap-order property (heapify_up)

​

​

9

10 of 40

Max-heap: Insertion

10

11 of 40

Max-Heap: Deletion

  • Removal of the root key (highest priority = maximum number) from the heap
  • The removal algorithm consists of 2 steps
    1. Replace the root key with the key of the last node.
    2. Restore the heap-order property (Heapify-down)

​

​

​

11

12 of 40

Max-Heap: Deletion

12

13 of 40

Max Heap: Heap sort

​

  1. Build a Max-Heap:
    1. Convert the array into a max-heap, ensuring the largest element is at the root.
    2. Complexity: O(n).�
  2. Extract Maximum:
    • Swap the root (largest element) with the last element.
    • Reduce heap size by 1 and restore the max-heap property (heapify-down).
    • Repeat until all elements are sorted.
    • Complexity: O(nlogn).

​

13

14 of 40

Max Heap: Heap sort

14

15 of 40

Max Heap: Heap sort

15

16 of 40

Max Heap: Heap sort

16

17 of 40

Max Heap: Heap sort

17

18 of 40

Max Heap: Heap sort

18

19 of 40

Max Heap: Heap sort

19

20 of 40

Max Heap: Heap sort

20

21 of 40

Building Heap

​

  1. Build a Min/Max-Heap:
    1. Convert the array into a min-heap, ensuring the smallest element is at the root.
    2. Complexity: O(n).�

Not O(n logn) ?

21

22 of 40

Building max Heap

3

6

5

0

8

2

1

9

Intermediate Node

Leaf Node (n/2)

Total: n node

3

5

6

8

1

0

2

9

    • To make root node heapify, left tree, right tree should be a heap
    • To make the entire tree a heap, heapfiy-down from the lower node
    • Leaf node is already a heap

0 1 2 3 4 5 6 7

22

23 of 40

Building max Heap

3

6

5

0

8

2

1

9

Intermediate Node

Leaf Node (n/2)

Total: n node

3

5

6

8

1

0

2

9

    • To make root node heapify, left tree, right tree should be a heap
    • To make the entire tree a heap, heapfiy-down from the lower node
    • Leaf node is already a heap

0 1 2 3 4 5 6 7

23

24 of 40

Building max Heap

3

6

5

0

8

2

1

9

Intermediate Node

Leaf Node (n/2)

Total: n node

3

5

6

8

1

9

2

0

    • To make root node heapify, left tree, right tree should be a heap
    • To make the entire tree a heap, heapfiy-down from the lower node
    • Leaf node is already a heap

0 1 2 3 4 5 6 7

24

25 of 40

Building max Heap

3

6

5

0

8

2

1

9

Intermediate Node

Leaf Node (n/2)

Total: n node

3

5

6

8

1

9

2

0

    • To make root node heapify, left tree, right tree should be a heap
    • To make the entire tree a heap, heapfiy-down from the lower node
    • Leaf node is already a heap

0 1 2 3 4 5 6 7

25

26 of 40

Building max Heap

3

6

5

0

8

2

1

9

Intermediate Node

Leaf Node (n/2)

Total: n node

3

5

6

8

1

9

2

0

    • To make root node heapify, left tree, right tree should be a heap
    • To make the entire tree a heap, heapfiy-down from the lower node
    • Leaf node is already a heap

0 1 2 3 4 5 6 7

26

27 of 40

Building max Heap

3

6

5

0

8

2

1

9

Intermediate Node

Leaf Node (n/2)

Total: n node

3

5

9

8

1

6

2

0

    • To make root node heapify, left tree, right tree should be a heap
    • To make the entire tree a heap, heapfiy-down from the lower node
    • Leaf node is already a heap

0 1 2 3 4 5 6 7

27

28 of 40

Building max Heap

3

6

5

0

8

2

1

9

Intermediate Node

Leaf Node (n/2)

Total: n node

3

5

9

8

1

6

2

0

    • To make root node heapify, left tree, right tree should be a heap
    • To make the entire tree a heap, heapfiy-down from the lower node
    • Leaf node is already a heap

0 1 2 3 4 5 6 7

28

29 of 40

Building max Heap

3

6

5

0

8

2

1

9

Intermediate Node

Leaf Node (n/2)

Total: n node

9

5

3

8

1

6

2

0

    • To make root node heapify, left tree, right tree should be a heap
    • To make the entire tree a heap, heapfiy-down from the lower node
    • Leaf node is already a heap

0 1 2 3 4 5 6 7

29

30 of 40

Building max Heap

3

6

5

0

8

2

1

9

Intermediate Node

Leaf Node (n/2)

Total: n node

9

5

8

3

1

6

2

0

    • To make root node heapify, left tree, right tree should be a heap
    • To make the entire tree a heap, heapfiy-down from the lower node
    • Leaf node is already a heap

0 1 2 3 4 5 6 7

30

31 of 40

Building max Heap

3

6

5

0

8

2

1

9

Intermediate Node

Leaf Node (n/2)

Total: n node

9

5

8

3

1

6

2

0

    • To make root node heapify, left tree, right tree should be a heap
    • To make the entire tree a heap, heapfiy-down from the lower node
    • Leaf node is already a heap

0 1 2 3 4 5 6 7

31

32 of 40

Building max Heap: Time Complexity

Number of nodes Height

1 3

​

2 2

​

4 1

​

​

8 0

Level 3

Level 2

Level 1

Level 0

 

32

33 of 40

Building max Heap: Time Complexity

Number of nodes Height

1 3

​

2 2

​

4 1

​

​

8 0

Level 3

Level 2

Level 1

Level 0

 

33

34 of 40

Building max Heap: Time Complexity

Number of nodes Height

1 3

​

2 2

​

4 1

​

​

8 0

Level 3

Level 2

Level 1

Level 0

 

34

35 of 40

Building max Heap: Time Complexity

Number of nodes Height

1 3

​

2 2

​

4 1

​

​

8 0

Level 3

Level 2

Level 1

Level 0

 

35

36 of 40

Building max Heap: Time Complexity

Number of nodes Height

1 3

​

2 2

​

4 1

​

​

8 0

Level 3

Level 2

Level 1

Level 0

 

36

37 of 40

37

38 of 40

38

39 of 40

Appendix

39

40 of 40

Homeworks

  1. 703. Kth Largest Element in a Stream — https://leetcode.com/problems/kth-largest-element-in-a-stream�
  2. 1046. Last Stone Weight — https://leetcode.com/problems/last-stone-weight�
  3. 1005. Maximize Sum Of Array After K Negations — https://leetcode.com/problems/maximize-sum-of-array-after-k-negations�
  4. 1337. The K Weakest Rows in a Matrix — https://leetcode.com/problems/the-k-weakest-rows-in-a-matrix�
  5. 506. Relative Ranks — https://leetcode.com/problems/relative-ranks (can be done with sorting + indices; no hash table needed)�
  6. 215. Kth Largest Element in an Array — https://leetcode.com/problems/kth-largest-element-in-an-array�
  7. 973. K Closest Points to Origin — https://leetcode.com/problems/k-closest-points-to-origin�
  8. 378. Kth Smallest Element in a Sorted Matrix — https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix

40