CS234 Lecture 15: Binary Trees.docx
7 Jun 2015
School
Department
Course
Professor
Document Summary
Binary tree based implementation of adt pq each node of the tree represents a node use complete tree root is highest priority idea: each parent has higher priority than all its children enqueue: add to the next open leaf, then check parents of that node repeatedly and switch the two nodes if priority is wrong dequeue: store root temporarily. This uses more memory and is less efficient largely because of finding or maintaining a reference to the last/next node runtimes (assuming extra capacity is already there: enqueue, dequeue: constant per bubble up (h) (can only bubble up at most h times) (log n) constant per bubble down (h) (only every swap with one of the children) (log n) Note: we skip 0 in the array implementation since it makes the doubling index (n) time (compared to (n log n) for n enqueues) trick to get children work a heap can be built in eg. input: [/,8,2,13,5,6,10,4,7,1,14] visualize:
