CS210 · Heaps · Annotated SlidesHeaps
Original
Overview

Heaps

Heaps (Goodrich): the priority queue ADT and PQ-sorting, heap-order and completeness, height, insertion with upheap, removal with downheap, heap-sort, array-based heaps, merging, and bottom-up construction in O(n).

How to read this page

Every original slide is shown unchanged. Yellow marks on a slide point to a numbered note: hover or tap a mark to jump to its note, and hover a note to see its marks. Questions tagged Past exam appeared on a real paper; Prediction questions are likely angles, not confirmed. Pick an answer to each question: a wrong pick tells you why it is wrong, so you can try again.

All 27 slides
  1. 1 Part-D2
  2. 2 Recall Priority Queue ADT ( § 7.1.3)
  3. 3 Recall Priority Queue Sorting ( § 7.1.4)
  4. 4 aheap the node
  5. 5 Slide 5
  6. 6 Slide 6
  7. 7 Slide 7
  8. 8 a.si wisias is isan
  9. 9 a r
  10. 10 Slide 10
  11. 11 Height of a Heap ( § 7.3.1)
  12. 12 Heaps and Priority Queues
  13. 13 Insertion into a
  14. 14 Upheap
  15. 15 Removal from a Heap ( § 7.3.3)
  16. 16 Slide 16
  17. 17 Downheap
  18. 18 Updating the Last Node
  19. 19 Heap-Sort ( § 2.4.4)
  20. 20 Vector-based Heap
  21. 21 Merging Two Heaps
  22. 22 Bottom-up Heap Construction ( § 2.4.3)
  23. 23 Example
  24. 24 Example (contd.)
  25. 25 Example (contd.)
  26. 26 Example (end)
  27. 27 Analysis
Slide 1 / 27

Part-D2

Slide 1: Part-D2
Slide 2 / 27

Recall Priority Queue ADT ( § 7.1.3)

Slide 2: Recall Priority Queue ADT ( § 7.1.3)
Slide 3 / 27

Recall Priority Queue Sorting ( § 7.1.4)

Slide 3: Recall Priority Queue Sorting ( § 7.1.4)
Slide 4 / 27

aheap the node

Slide 4: aheap the node
Slide 5 / 27

Slide 5

Slide 5: Slide 5
Slide 6 / 27

Slide 6

Slide 6: Slide 6
Slide 7 / 27

Slide 7

Slide 7: Slide 7
Slide 8 / 27

a.si wisias is isan

Slide 8: a.si wisias is isan
Slide 9 / 27

a r

Slide 9: a r
Slide 10 / 27

Slide 10

Slide 10: Slide 10
Slide 11 / 27

Height of a Heap ( § 7.3.1)

Slide 11: Height of a Heap ( § 7.3.1)
Slide 12 / 27

Heaps and Priority Queues

Slide 12: Heaps and Priority Queues
Slide 13 / 27

Insertion into a

Slide 13: Insertion into a
Slide 14 / 27

Upheap

Slide 14: Upheap
Slide 15 / 27

Removal from a Heap ( § 7.3.3)

Slide 15: Removal from a Heap ( § 7.3.3)
Slide 16 / 27

Slide 16

Slide 16: Slide 16
Slide 17 / 27

Downheap

Slide 17: Downheap

Notes

  1. Downheap after removeMin: swap down with the smaller child → O(log n).

Slide 18 / 27

Updating the Last Node

Slide 18: Updating the Last Node
Slide 19 / 27

Heap-Sort ( § 2.4.4)

Slide 19: Heap-Sort ( § 2.4.4)

Exam angle

PredictionQ1

Heap-sort runs in:

Slide 20 / 27

Vector-based Heap

Slide 20: Vector-based Heap
Slide 21 / 27

Merging Two Heaps

Slide 21: Merging Two Heaps
Slide 22 / 27

Bottom-up Heap Construction ( § 2.4.3)

Slide 22: Bottom-up Heap Construction ( § 2.4.3)

Exam angle

PredictionQ1

Bottom-up heap construction takes O(n log n) and cannot be faster.

Slide 23 / 27

Example

Slide 23: Example
Slide 24 / 27

Example (contd.)

Slide 24: Example (contd.)
Slide 25 / 27

Example (contd.)

Slide 25: Example (contd.)
Slide 26 / 27

Example (end)

Slide 26: Example (end)
Slide 27 / 27

Analysis

Slide 27: Analysis