CSE 116 Lecture Notes - Lecture 38: Binary Tree, Priority Queue

• School: University at Buffalo
• Department: Computer Science & Engineering
• Course: CSE 116
• Professor: Matthew Hertz

Document Summary

Collection used by programs to process elements in order of importance. Elements removed from smallest to largest (smaller == more important) Require comparable elements or use of a comparator. List-based implementation excels at remove(: but add() speed sucks as result of trade-off made. But we will need to add element before removing it: wrong method improved remove() limited by add() Clicker question: 2nd most important element location: list element at index 0, node following most important element, list element at index 1, question meaningless; only most important element available answer: d. question meaningless; only most important element available. Binary tree used to implement priority queue: nodes still organized using parent-child relationship, at most 2 children & 1 parent for each node in tree. Heaps specify 2 more properties for binary tree: node"s ele(cid:373)e(cid:374)t (cid:373)ore important tha(cid:374) child(cid:396)e(cid:374)"s ele(cid:373)e(cid:374)ts, binary tree structure must be complete binary tree.