COMS W3134 Lecture Notes - Lecture 13: Binary Heap, Priority Queue, Binary Tree
Document Summary
Heap = priority queue: tree is always complete height : ol log n i. Each node satisfies the heap order condition min heap parent is less than or equal to its child . Min - heap ordered insert ii delete min l ) I chapter 6 16. 1 - 6. 31 if parents. 4 link to parents i kind of ) Right child 2 * it i. 10 reserve space in ttsize check if parents insert. If false , swap parent eiinsrt ( percolate up : make sure complete first, make changes to maintain heap rules ( check parents insert ) cost - olheightl. 22 deletemint ) 3: try to replace with rightmost leaf. Check min of childrens rightmost leaf cost : ollogh ) ( percolate down ) , only need to compare with only child sorted list heap : continuously delete mint ) cost : oln - login ) think how thing can change.