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

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…