## Heaps

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.

### Applications

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.

### Special Heaps

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(dlog_{d}N).
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.

Last update: 7/22/13