CS210 · Heaps · Annotated SlidesHeaps and Priority Queues
Original
Overview

Heaps and Priority Queues

The priority queue API and applications, elementary implementations, complete binary trees, binary heaps in an array, swim (promotion) and sink (demotion), and the cost summary.

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 21 slides
  1. 1 A l g o r i t h m s
  2. 2 Slide 2
  3. 3 Collections
  4. 4 Priority queue
  5. 5 Priority queue API
  6. 6 Priority queue applications
  7. 7 Priority queue elementary implementations
  8. 8 Slide 8
  9. 9 Complete binary tree
  10. 10 Slide 10
  11. 11 A complete binary tree in nature
  12. 12 Binary heap representations
  13. 13 Binary heap properties
  14. 14 Binary heap demo
  15. 15 Binary heap demo
  16. 16 Promotion in a heap
  17. 17 Insertion in a heap
  18. 18 Demotion in a heap
  19. 19 Delete the maximum in a heap
  20. 20 Binary heap: Java implementation
  21. 21 Priority queues implementation cost summary
Slide 1 / 21

A l g o r i t h m s

Slide 1: A l g o r i t h m s
Slide 2 / 21

Slide 2

Slide 2: Slide 2
Slide 3 / 21

Collections

Slide 3: Collections
Slide 4 / 21

Priority queue

Slide 4: Priority queue
Slide 5 / 21

Priority queue API

Slide 5: Priority queue API
Slide 6 / 21

Priority queue applications

Slide 6: Priority queue applications
Slide 7 / 21

Priority queue elementary implementations

Slide 7: Priority queue elementary implementations

Notes

  1. Unordered array: insert O(1), delMax O(N). Ordered array: insert O(N), delMax O(1). Binary heap: both O(log N).

Exam angle

PredictionQ1

With a binary heap, insert and delete-max are:

Slide 8 / 21

Slide 8

Slide 8: Slide 8
Slide 9 / 21

Complete binary tree

Slide 9: Complete binary tree
Slide 10 / 21

Slide 10

Slide 10: Slide 10
Slide 11 / 21

A complete binary tree in nature

Slide 11: A complete binary tree in nature
Slide 12 / 21

Binary heap representations

Slide 12: Binary heap representations
Slide 13 / 21

Binary heap properties

Slide 13: Binary heap properties

Notes

  1. Heap-ordered: every parent ≥ its children (max-heap). Array: parent of k is k/2; children 2k, 2k + 1.

Exam angle

PredictionQ1

In a 1-based heap array, the parent of the node at index 9 is at:

Slide 14 / 21

Binary heap demo

Slide 14: Binary heap demo
Slide 15 / 21

Binary heap demo

Slide 15: Binary heap demo
Slide 16 / 21

Promotion in a heap

Slide 16: Promotion in a heap
Slide 17 / 21

Insertion in a heap

Slide 17: Insertion in a heap

Notes

  1. Insert: add at the end, swim up while larger than parent.

Slide 18 / 21

Demotion in a heap

Slide 18: Demotion in a heap
Slide 19 / 21

Delete the maximum in a heap

Slide 19: Delete the maximum in a heap

Notes

  1. Delete max: swap root with the last item, remove it, sink the new root.

Slide 20 / 21

Binary heap: Java implementation

Slide 20: Binary heap: Java implementation
Slide 21 / 21

Priority queues implementation cost summary

Slide 21: Priority queues implementation cost summary