Skip to main content

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()



Comments

Popular posts from this blog

Stretch a row if data overflows in jasper reports

It is very common that some columns of the report need to stretch to show all the content in that column. But  if you just specify the property " stretch with overflow' to that column(we called text field in jasper report world) , it will just stretch that column and won't change other columns, so the row could be ridiculous. Haven't find the solution from internet yet. So I just review the properties in iReport one by one and find two useful properties(the bold highlighted in example below) which resolve the problems.   example:
<band height="20" splitType="Stretch"> <textField isStretchWithOverflow="true" pattern="" isBlankWhenNull="true"> <reportElement stretchType="RelativeToTallestObject" mode="Opaque" x="192" y="0" width="183" height="20"/> <box leftPadding="2"> <pen lineWidth="0.25"/> …

JasperReports - Configuration Reference

Live - solving the jasper report out of memory and high cpu usage problems

I still can not find the solution. So I summary all the things and tell my boss about it. If any one knows the solution, please let me know.


Symptom: 1.The JVM became Out of memory when creating big consumption report 2.Those JRTemplateElement-instances is still there occupied even if I logged out the system
Reason:         1. There is a large number of JRTemplateElement-instances cached in the memory 2.The clearobjects() method in ReportThread class has not been triggered when logging out
Action I tried:      About the Virtualizer: 1.Replacing the JRSwapFileVirtualizer with JRFileVirtualizer 2.Not use any FileVirtualizer for cache the report in the hard disk Result: The japserreport still creating the a large number of JRTemplateElement-instances in the memory     About the work around below,      I tried: item 3(in below work around list) – result: it helps to reduce  the size of the JRTemplateElement Object                Item 4,5 – result : it helps a lot to reduce the number of  JRTemplateE…