Two Heaps, Side by Side

We now have two implementations of the PriorityQueue contract, both binary heaps. Here are their costs:

Operation	`LinkedHeap`	`ArrayHeap`
`size`	$O (1)$	$O (1)$
`peek`	$O (1)$	$O (1)$
`add`	$O (lo g n)$	$O (lo g n)$ amortized
`remove`	$O (lo g n)$	$O (lo g n)$

The only difference in Big-Oh is that the array’s add is amortized, because now and then it doubles the backing array.

The two heaps hold the same tree and make the same swaps. They differ in the work around the swaps. ArrayHeap finds the next open slot and the last node in one step, where LinkedHeap follows a path down from the root. So on ArrayHeap, an add whose value does not climb is $O (1)$ , apart from the occasional resize: the new element goes at index $n$ , swim compares it with its parent once, and it stops. Memory is the same trade-off we saw in the stack chapter: the array has spare slots, and the linked version has one node per element. Here each node holds two references, left and right.

Which one to use

The array is the usual way to store a binary heap. A heap is always a complete tree, so the array has no gaps, and every move around the tree is index arithmetic. Java’s own PriorityQueue is a binary heap stored in an array.