Comparing the Two Heaps

LinkedHeap and ArrayHeap both implement PriorityQueue<T> (size, peek, add, remove) as a binary heap. LinkedHeap stores each element in a node with left and right references. ArrayHeap stores the tree in level order in an array that doubles in length when it fills.

Solution

peek is $O (1)$ in both.
add is $O (lo g n)$ in LinkedHeap and $O (lo g n)$ amortized in ArrayHeap, because the array occasionally doubles.
remove is $O (lo g n)$ in both.

Solution

In LinkedHeap it is $O (lo g n)$ : add still follows the path from the root down to the open slot. In ArrayHeap it is $O (1)$ amortized: the element goes at index $n$ , swim compares it with its parent once, and it stops.

Solution

LinkedHeap creates one node object per element, and each node has two child references. ArrayHeap has no node objects and no child references, but its array can have spare slots, up to about half of it right after a doubling.

Solution

A heap is always a complete tree, so the array has no gaps. Every move between a node and its parent or children is index arithmetic. The next open slot and the last node are also at known indices, so no operation has to follow a path down from the root to find a slot.