1 of 39

Lecture 12:�Priority Queue & Heap (Continue)

2 of 39

Priority Queue

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

2

3 of 39

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 39

Priority Queue

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

Key

​

Value

4

5 of 39

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

5

6 of 39

Heap

6

7 of 39

Binary Heap

Min Heap

Max Heap

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

 

7

8 of 39

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)

​

​

8

9 of 39

Max-heap: Insertion

9

10 of 39

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)

​

​

​

10

11 of 39

Max-Heap: Deletion

11

12 of 39

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).

​

12

13 of 39

Max Heap: Heap sort

13

14 of 39

Max Heap: Heap sort

14

15 of 39

Max Heap: Heap sort

15

16 of 39

Max Heap: Heap sort

16

17 of 39

Max Heap: Heap sort

17

18 of 39

Max Heap: Heap sort

18

19 of 39

Max Heap: Heap sort

19

20 of 39

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) ?

20

21 of 39

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

21

22 of 39

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 39

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

23

24 of 39

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 39

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 39

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

26

27 of 39

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 39

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

28

29 of 39

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

29

30 of 39

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 39

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

 

31

32 of 39

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 39

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 39

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 39

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 39

36

37 of 39

37

38 of 39

Appendix

38

39 of 39

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

39