CS210 · Annotated SlidesHeaps — Heaps and Priority Queues
Heaps · Annotated slides

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.

Slide text Study notes Highlight: key words Tips, tricks & traps Seen again elsewhere How it can come up
Slide 1: A l g o r i t h m s
Exam weight Low
    Slide 2: Slide 2
    Exam weight Low
      Slide 3: Collections
      Exam weight Low
        Slide 4: Priority queue
        Exam weight Low
          Slide 5: Priority queue API
          Exam weight Low
          1. MaxPQ: insert, delMax, isEmpty.
          Slide 6: Priority queue applications
          Exam weight Low
            Slide 7: Priority queue elementary implementations
            Exam weight High
            1. Unordered array: insert O(1), delMax O(N). Ordered array: insert O(N), delMax O(1). Binary heap: both O(log N).
            🎯 How this can come up · 1 question
            MCQ

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

            Slide 8: Slide 8
            Exam weight Low
              Slide 9: Complete binary tree
              Exam weight Low
              1. Complete binary tree: perfectly balanced except the bottom level, filled left to right; height ⌊lg N⌋.
              Slide 10: Slide 10
              Exam weight Low

                A complete binary tree in nature

                11
                Exam weight Low
                  Slide 12: Binary heap representations
                  Exam weight Low
                    Slide 13: Binary heap properties
                    Exam weight High
                    1. Heap-ordered: every parent ≥ its children (max-heap). Array: parent of k is k/2; children 2k, 2k + 1.
                    🎯 How this can come up · 1 question
                    MCQ

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

                    Slide 14: Binary heap demo
                    Exam weight Low
                      Slide 15: Binary heap demo
                      Exam weight Low
                        Slide 16: Promotion in a heap
                        Exam weight Low
                          Slide 17: Insertion in a heap
                          Exam weight Low
                          1. Insert: add at the end, swim up while larger than parent.
                          Slide 18: Demotion in a heap
                          Exam weight Low
                            Slide 19: Delete the maximum in a heap
                            Exam weight Low
                            1. Delete max: swap root with the last item, remove it, sink the new root.
                            Slide 20: Binary heap: Java implementation
                            Exam weight Low
                              Slide 21: Priority queues implementation cost summary
                              Exam weight Low