public int iData; public HeapNode parent; public HeapNode leftChild; public HeapNode rightChild;Each node in the heap will be an object belonging to the HeapNode class. The Heap class itself has the following two data members.
protected HeapNode root; protected HeapNode lastNode;These two data members are references that provide access to the root (top) of the heap and to the last node in the heap. Let us try to implement the insert function for this new implementation of a heap. Here is an incomplete implementation of the insert function.
public void insert(int key) { // Creates a new HeapNode object with key in the // iData field, and with parent, leftChild, and // rightChild, all pointing to null HeapNode newNode = new HeapNode(key); MISSING CODE FOR INSERTING THE NEW NODE AS THE LAST NODE OF THE HEAP trickleUp(lastNode); } // end insert()Supply the missing code for inserting the new node as the last node of the heap. When the heap was implemented as an array, making a new node the last node was simply a matter of assigning the new node to the slot in the array indexed by currentSize. In the current implementation, given the current last node, finding where the new node should go is not as simple.
void leftRotate(Node pivotNode, Node parentNode)pivotNode is where the rotation takes place; pivotNode can be the left child or the right child of parentNode. The following picture shows a left rotation and clarifies what the above function is supposed to do.
Recall that each Node object in a binary search tree, as implemented by Lafore, contains the following data members.
public int iData; // data item (key) public double dData; // data item public Node leftChild; // this node's left child public Node rightChild; // this node's right child