Weiss Ch. 6
Priority Queues are a natural and simple idea, and heaps (aka complete binary trees) are a natural and simple data structure for them. Because of the complete binary tree's characteristics it can be implemented without pointers in an array, with nodes written in levelwise: Numbers in this tree are their heap array indices (+1?)
1
2 3
4 5 6 7
...
The element at i has its left child at 2i, right child at 2i+1, and parent at ⌊i/2⌋.
Basics not deep, not hard.
Of course THAT'S no good, so back half of chapter has the usual menagerie of specialized and more esoteric related data structures.
Weiss Ch. 6.4
1. Re-solve the selection problem (find kth-largest or -smallest element in a set of numbers). Heapify and deleteMax (Min) solve in NlogN time. Promise of an O(N) average time next chapter, and in Ch 10 an elegant but impractical O(N) (worst-case) method. Sounds intriguing: simple problem inspires deep algorithmic thinking...
2. Simulations. Hugely important computational tool (e.g. in systems, AI, physics, chemistry, etc. etc.). Can simulate the problem a "tick" per simulation cycle, but that's wasteful if nothing much is happening most of the time. An "event-driven" simulation using p-queues can create future events (schedule a simulated customer random future arrival and departure times). Then using p-queue with event time as the priority can simulate all and only the interesting events in the order they occur.
Weiss Ch. 6.5, - 6.8
1. d-Heaps are simply heaps implemented with d-ary trees. They're shallower than corresponding binary trees, so inserts are quicker, but deleteMin has to search thru d children, which in general is O(dlogdN). Good for big heaps on disk. Maybe 4 heaps better than binary?
2. Merging Heaps. Can we merge heaps in o(N) time? Array implementation implies Θ(N) time, so now use pointers. Leftist heaps and skew heaps are good for implementing merges. As usual, We get diagrams, code, and descriptive prose from Weiss. Finally, binomial heaps support merging, insertion, deleteMin, in O(logN) worst case but also can insert in constant O(1) average time. Again the usual treatment in text.
