CSC148H1 Lecture Notes - Priority Queue
1
CSC148H1 Full Course Notes
Verified Note
1 document
Document Summary
Heap properties: all heaps have two major properties: structure property: All heaps are complete trees, assumed to be binary trees. Complete tree = all levels are filled except for the last one, which is filled from left to right: heap-order property: (assuming min-heap) every element"s priority value is smaller than the than the priority values of the elements below it. Left child = current position * 2+1. Right child = current position*2 + 2: complete tree efficient use of space, quick to find key positions: Last element (for remove) = len(heap) 1. Heap insert: to insert an element into the heap, observe structure property first, then resolve heap-order property. Add new element to first empty spot in the complete tree. Then bubble the element up (towards the root) until the priority value of the parent is smaller than its own. Heap remove: always remove from the root, again, maintain structure property first, and then heap-order property.
