Java - Data Structure (Heap)

A priority queue is an ADT offering methods that allow removal of the item with the maximum(or minimum) key value, and sometimes other activities. Can be implemented as an array or heap.
Efficiency: deletion(using array) O(1), insertion(array) O(N)
deletion and insertion (heap): O(LogN)

Heap(be used to implement a priority queue) is a kind of tree. It offers both insertion and deletion in O(logN) time. Thus it's not quite as fast for deletion, but much fast for insertion. It's the method of choice for implementing priority queues where speed is important and there will be many insertion.

don't confuse the term heap, used here for a special kind of binary tree, with the same term used to mean the portion of computer memory available to a programmer with new in languages like Java and C++;


class Node
{
public int iData; // data item (key)
public Node(int key) // constructor
{ iData = key; }
} // 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].iData < bottom.iData )
{
heapArray[index] = heapArray[parent]; // move it down
index = parent;
parent = (parent-1) / 2;
} // end while
heapArray[index] = bottom;
} // end trickleUp()