Unit 9 Chapter 12 Heaps Code Flashcards
1
Q
heap
A
//////////////////////////////////////////////////////////////// class Node { private int iData; // data item (key) // ------------------------------------------------------------- public Node(int key) // constructor { iData = key; } // ------------------------------------------------------------- public int getKey() { return iData; } // ------------------------------------------------------------- public void setKey(int id) { iData = id; } // ------------------------------------------------------------- } // end class Node //////////////////////////////////////////////////////////////// class Heap { private Node[] heapArray; private int maxSize; // size of array private int currentSize; // number of nodes in array // ------------------------------------------------------------- public Heap(int mx) // constructor { maxSize = mx; currentSize = 0; heapArray = new Node[maxSize]; // create array } // ------------------------------------------------------------- public boolean isEmpty() { return currentSize==0; } // ------------------------------------------------------------- public boolean insert(int key) { if(currentSize==maxSize) return false; Node newNode = new Node(key); heapArray[currentSize] = newNode; trickleUp(currentSize++); return true; } // end insert() // ------------------------------------------------------------- public void trickleUp(int index) { int parent = (index-1) / 2; Node bottom = heapArray[index];
while( index > 0 && heapArray[parent].getKey() > bottom.getKey() ) { heapArray[index] = heapArray[parent]; // move it down index = parent; parent = (parent-1) / 2; } // end while heapArray[index] = bottom; } // end trickleUp() // ------------------------------------------------------------- public Node remove() // delete item with max key { // (assumes non-empty list) Node root = heapArray[0]; heapArray[0] = heapArray[--currentSize]; trickleDown(0); return root; } // end remove() // ------------------------------------------------------------- public void trickleDown(int index) { int largerChild; Node top = heapArray[index]; // save root while(index < currentSize/2) // while node has at { // least one child, int leftChild = 2*index+1; int rightChild = leftChild+1; // find larger child if(rightChild < currentSize && // (rightChild exists?) heapArray[leftChild].getKey() < heapArray[rightChild].getKey()) largerChild = rightChild; else largerChild = leftChild; // top >= largerChild? if( top.getKey() =currentSize) return false; int oldValue = heapArray[index].getKey(); // remember old heapArray[index].setKey(newValue); // change to new
if(oldValue < newValue) // if raised, trickleUp(index); // trickle it up else // if lowered, trickleDown(index); // trickle it down return true; } // end change() // ------------------------------------------------------------- public void displayHeap() { System.out.print("heapArray: "); // array format for(int m=0; m 0) // for each heap item { if(column == 0) // first item in row? for(int k=0; k); } // end switch } // end while } // end main() //------------------------------------------------------------- public static String getString() throws IOException { InputStreamReader isr = new InputStreamReader(System.in); BufferedReader br = new BufferedReader(isr); String s = br.readLine(); return s; } //------------------------------------------------------------- public static char getChar() throws IOException { String s = getString(); return s.charAt(0); } //------------------------------------------------------------- public static int getInt() throws IOException { String s = getString(); return Integer.parseInt(s); } //------------------------------------------------------------- } // end class HeapApp ////////////////////////////////////////////////////////////////