CS210 · Annotated SlidesHeaps — Heaps
Heaps · Annotated slides

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

Slide text Study notes Highlight: key words Tips, tricks & traps Seen again elsewhere How it can come up
Slide 1: Slide 1
Exam weight Low
    Slide 2: Recall Priority Queue ADT ( § 7.1.3)
    Exam weight Low
      Slide 3: Recall Priority Queue Sorting ( § 7.1.4)
      Exam weight Low
        Slide 4: aheap the node
        Exam weight Low
        1. Heap: heap-order (key(v) ≥ key(parent(v)) for a min-heap) and a complete binary tree.
        Slide 5: Slide 5
        Exam weight Low
          Slide 6: Slide 6
          Exam weight Low
            Slide 7: Slide 7
            Exam weight Low
              Slide 8: Slide 8
              Exam weight Low
                Slide 9: Slide 9
                Exam weight Low
                  Slide 10: Slide 10
                  Exam weight Low
                    Slide 11: Height of a Heap ( § 7.3.1)
                    Exam weight Low
                    1. A heap with n keys has height O(log n).
                    Slide 12: Heaps and Priority Queues
                    Exam weight Low
                      Slide 13: Insertion into a
                      Exam weight Low
                        Slide 14: Upheap
                        Exam weight Low
                        1. Upheap after insertion: swap up while the key is smaller than its parent → O(log n).
                        Slide 15: Removal from a Heap ( § 7.3.3)
                        Exam weight Low
                          Slide 16: Slide 16
                          Exam weight Low
                            Slide 17: Downheap
                            Exam weight Low
                            1. Downheap after removeMin: swap down with the smaller child → O(log n).
                            Slide 18: Updating the Last Node
                            Exam weight Low
                              Slide 19: Heap-Sort ( § 2.4.4)
                              Exam weight High
                              1. Heap-sort: n inserts + n removeMins → O(n log n).
                              🎯 How this can come up · 1 question
                              MCQ

                              Heap-sort runs in:

                              Slide 20: Vector-based Heap
                              Exam weight Low
                                Slide 21: Merging Two Heaps
                                Exam weight Low
                                  Slide 22: Bottom-up Heap Construction ( § 2.4.3)
                                  Exam weight High
                                  1. Bottom-up construction builds a heap from n keys in O(n).
                                  🎯 How this can come up · 1 question
                                  True / False

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

                                  Slide 23: Example
                                  Exam weight Low
                                    Slide 24: Example (contd.)
                                    Exam weight Low
                                      Slide 25: Example (contd.)
                                      Exam weight Low
                                        Slide 26: Example (end)
                                        Exam weight Low
                                          Slide 27: Analysis
                                          Exam weight Low