COMP 352 Lecture 17: Priority Queue

• School: Concordia University
• Department: Computer Sci.
• Course: COMP 352
• Professor: T B A

Document Summary

Depending on the implementation used it affects the time complexity. The ones we have so far were proper binary tree. A heap complete binary tree stores keys, which satisfy the following properties. Heap order property: max: for every node valueother than root, key(value) <= key(parent(value)) Min: for every node valueother than root, key(value) >= key(parent(value)) ii. Let x be the height of the binary tree, then: the remaining nodes at depth h reside in the left most possible position in that. For i = 0, 1, h-1, there are 2inodes at depth i. Insertion takes place from left ii: the minimum is always at the root. Adding a value that is larger than parent causes upheap to execute. Upon doing this, the heap order property is not valid anymore. If the child is smaller than the parent, then you swap the parent with that child.