Linked heap

A linked heap is an actual binary tree where every node holds references to its children. We first create a skeleton structure for our heap:

public class LinkedHeap<E> implements PriorityQueue<E>{

    protected static class Node<E>{
        protected E value;
        protected Node<E> left;
        protected Node<E> right;
        protected Node<E> parent;
        public Node(E value, Node<E> parent){
            this.value = value;
            this.parent = parent;
        }
    }
    …
}

To keep track of the next position, each position is given a number, just like we did in our array-based representation. We have the same calculation for the index of the parent and children. But, in this case, looking up the value at a particular index requires a traversal from the root to that node. We create a method to do this. Note that since we are not using an array, the position starts from 1. We start by finding the parent node recursively....