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

Spring - Operations with jdbcTemplate

This class manages all the database communication and exception handling using a java.sql.Connection that is obtained from the provided DataSource. JdbcTemplate is a stateless and threadsafe class and you can safely instantiate a single instance to be used for each DAO.


Use of Callback Methods
JdbcTemplate is based on a template style of programming common to many other parts of Spring. Some method calls are handled entirely by the JdbcTemplate, while others require the calling class to provide callback methods that contain the implementation for parts of the JDBC workflow. This is another form of Inversion of Control. Your application code hands over the responsibility of managing the database access to the template class. The template class in turn calls back to your application code when it needs some detail processing filled in. These callback methods are allowed to throw a java.sql.SQLException, since the framework will be able to catch this exception and use its built-in excepti…