I&C SCI 46 Lecture Notes - Lecture 11: Priority Queue, Binary Logarithm, Sorting Algorithm

• School: UC-Irvine
• Department: Information and Computer Science
• Course: I&C SCI 46
• Professor: Richard Pattis

Document Summary

Heaps for priority queues and o(n log2 n) sorting. We will next study heaps (this lecture) and avl trees (the next lecture). Both of these are special kinds of trees that have interesting order/structure properties that are different from binary search trees. They both use similar rules when adding/removing values from these trees, and then restoring their properties. Heaps (this term has another important use in computer science: memory used for allocating the storage for objects when the new operator is used) are almost the perfect data structure for storing priority queues. By using heaps we can add a value in o(log2 n) and also remove the highest priority value in. The reason for these complexity classes: heaps always stay perfectly balanced, unlike bsts. In the discussion below i will characterize min-heaps and the algorithms that process them. We would use max-heaps, which are appropriate for storing priority queues: their operations follow almost identical/flipped rules.