Skip to main content

Create Binary Heap sorting by using Java

binary heap is a set of nodes with keys arranged in a complete heap-ordered binary tree


A binary tree is heap-ordered if the key in each node is larger than (or equal to) the keys in that nodes two children (if any).


Rule: 
In a heap, the parent of the node in position k is in position k/2; and, conversely, the two children of the node in position k are in positions 2k and 2k + 1. We can travel up and down by doing simple arithmetic on array indices: to move up the tree from a[k] we set k to k/2; to move down the tree we set k to 2*k or 2*k+1.


Top-down heapify (sink). If the heap order is violated because a node's key becomes smaller than one or both of that node's children's keys, then we can make progress toward fixing the violation by exchanging the node with the larger of its two children. This switch may cause a violation at the child; we fix that violation in the same way, and so forth, moving down the heap until we reach a node with both children smaller, or the bottom.






public class Heap {

    public static void main(String[] args) {
        String[] a = new String[]{
        "C","Z","S", "O","R","T", "E", "X", "A", "M", "P", "L", "E", "A","F"
        };
        Heap.sort(a);

       
        Integer[] b = new Integer[]{10,8,7,1,2,4,3,6,5};
        Heap.sort(b);
     
    }
   
public static void sort(Comparable[] pq) {
       int N = pq.length;
     
       //build the heap
       // start from 1 to N/2, as the bottom level(which N located with be sorted by sink method;
       for (int k = N/2; k >= 1; k--){
           sink(pq, k, N);
       }
       
       //sort the array
       while (N > 1) {
        //in place sorting, exchange the top(max or min) with the bottom value, and re-organzie the heap(N-1) again.
           exch(pq, 1, N--);
           sink(pq, 1, N);
       }    
       show(pq);
 
   }

  /***********************************************************************
   * Helper functions to restore the heap invariant.
   **********************************************************************/
   private static void sink(Comparable[] pq, int k, int N) {
       while (2*k <= N) {
           int j = 2*k;
           if (j < N && less(pq, j, j+1)) j++;
           if (!less(pq, k, j)) break;
           exch(pq, k, j);
           k = j;
       }
   }

  /***********************************************************************
   * Helper functions for comparisons and swaps.
   * Indices are "off-by-one" to support 1-based indexing.
   **********************************************************************/
   private static boolean less(Comparable[] pq, int i, int j) {
       return pq[i-1].compareTo(pq[j-1]) < 0;
   }

   private static void exch(Object[] pq, int i, int j) {
       Object swap = pq[i-1];
       pq[i-1] = pq[j-1];
       pq[j-1] = swap;
   }

   // print array to standard output
   private static void show(Comparable[] a) {
       for (int i = 0; i < a.length; i++) {
           System.out.print(a[i] + " ");
        }  
       System.out.println();
    }
}


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…