Home IT Linux Windows Database Network Programming Server Mobile  
           
  Home \ Programming \ Java implementation heap sort (large root heap)     - Oracle database import and export (Database)

- 25 Git Usage Tips (Linux)

- To build a private Docker registry (Server)

- Repair Chrome for Linux is (Linux)

- 20 Linux commands interview questions and answers (Linux)

- Android recyclerview cardview (Programming)

- Ubuntu installed Komodo editor by PPA (Linux)

- Git bulk delete remote tag (Linux)

- How to turn Java String into Date (Programming)

- MySQL main and backup replication structures (using mysqld_multi) (Database)

- Linux kernel RCU (Read Copy Update) lock Brief - prequel (Linux)

- Two kinds of agents of Spring AOP (Programming)

- Compile and install Memcached can not find GCC (Programming)

- Linux three ways to set environment variables (Linux)

- MySQL time field based partitioning scheme summary (Database)

- RHEL5 / 6 Installation Notes (Linux)

- Debian 7.6 install Nvidia graphics driver (Linux)

- Install Firefox 28 on Ubuntu, Linux Mint (Linux)

- Android to determine whether the device to open WIFI, GPRS data connection (Programming)

- Kali Linux 2.0 U disk installation errors Your installation cd-rom could not be mounted (Linux)

 
         
  Java implementation heap sort (large root heap)
     
  Add Date : 2017-08-31      
         
       
         
  Heap sort is a tree selection sort method, which is characterized by: the sorting process, the array [0, ..., n-1] as a complete binary tree sequential storage structure, the use of complete binary tree internal parent node and child relationship between nodes, choose keywords maximum (minimum) element in the current disorder in the area.

1. If array [0, ..., n-1] represents a complete binary tree stored in the order mode, the inherent relationship between parent and child node pointer node pointer is as follows:

Any node pointer i: parent: i == 0 null:? (I-1) / 2

Left Children: 2 * i + 1

Right Children: 2 * i + 2

2. The definition of the heap: n keyword sequence array [0, ..., n-1], if and only if the following requirements are met: (0 < = i < = (n-1) / 2)

1. array [i] < = array [2 * i + 1] and array [i] < = array [2 * i + 2]; root called small heap;

2. array [i]> = array [2 * i + 1] and array [i]> = array [2 * i + 2]; I called large root heap;

3. The establishment of large root heap:

Complete binary tree with n nodes array [0, ..., n-1], the last node n-1 is the first (n-1-1) Children / 2 nodes. The first (n-1-1) / 2 nodes to adjust the sub-tree root, so that the sub-tree called the heap.

For large root heap adjustment method is: If [root keyword] is less than [children around the greater keyword], then the switch.

After forward successively for each node ((n-2) / 2 - 1) ~ 0 rooted subtrees adjustment to see if the node value is about greater than the value of the child node, if it is, the more the left and right child nodes Great value to exchange, could undermine the heap after switching to the next level, then continue using the above method to build the next level of the stack, the stack until the node to the root of the subtree constitution.

Repeated use of the above adjustments heap pile construction method until the root node.

4. heap sort :( large root heap)

. A will be stored in array [0, ..., n-1] n elements in the completion of the initial heap;

. B element will be top of the heap and stack bottom element exchange, the maximum value of the sequence is already in the right place;

c. But this time the reactor was destroyed, the top of the heap element adjusted downward so that it continued to maintain a large root heap of nature, and then repeat step (2)(3), up until the heap, leaving only one element.

Heap sort algorithm performance analysis:

Space complexity: o (1);

Time Complexity: built heap: o (n), each adjustment o (log n), it is the best, the worst, the average case: o (n * logn);

Stability: Unstable

Establish large root heap method:

// Build large root heap: the array as a complete binary tree structure stored in the order
    private int [] buildMaxHeap (int [] array) {
        // Start from the last node of the parent node array.length-1 (array.length-1-1) / 2, until the root 0, repeatedly adjust the heap
        for (int i = (array.length-2) / 2; i> = 0; i -) {
            adjustDownToUp (array, i, array.length);
        }
        return array;
    }
    
    // The element array [k] from the bottom up gradually adjust the tree structure
    private void adjustDownToUp (int [] array, int k, int length) {
        int temp = array [k];
        for (int i = 2 * k + 1; i < length-1; i = 2 * i + 1) {// i is initialized to the left child node k, node along the larger child node downward adjustment
            if (i < length && array [i] < array [i + 1]) {// get the larger node child node subscript
                i ++; // if the right child node> left child, then take the right child node subscript
            }
            if (temp> = array [i]) {// root node> = about children keyword is greater, the adjustment is completed
                break;
            } Else {// the root < children around the greater keyword
                array [k] = array [i]; // left and right child nodes is greater array [] adjusted to the parent node
                k = i; // [key] to modify the value of k, to continue to adjust downward
            }
        }
        array [k] = temp; // value to be adjusted node release the final position
    }

HEAPSORT:

// Heap sort
    public int [] heapSort (int [] array) {
        array = buildMaxHeap (array); // initial construction heap, array [0] for the first trip to the value of the largest element
        for (int i = array.length-1; i> 1; i -) {
            int temp = array [0]; // the top of the heap and stack elements low exchange element, to obtain the correct current ranking position of the largest element
            array [0] = array [i];
            array [i] = temp;
            adjustDownToUp (array, 0, i); // sort the remaining elements of finishing piles
        }
        return array;
    }

Remove top of the heap element (ie, the maximum value of the sequence): The last element of the first stack element exchange with the top of the heap, because this time the nature of the heap is destroyed, the need for this time of the root node downward adjustment operation.

// Delete the top of the heap element operation
    public int [] deleteMax (int [] array) {
        // The last element of the heap and stack top element of the exchange, the end of the heap element value is set to -99999
        array [0] = array [array.length-1];
        array [array.length-1] = -99999;
        // At this time of the root node downward adjustment
        adjustDownToUp (array, 0, array.length);
        return array;
    }

Insertion operation of the heap: first new node on the end of the stack, and then adjust the operation of the new node performs upward.

The last element of the array is assumed that array [array.length-1] is empty, the new node is inserted initially placed here.

// Insert: To a large root heap array insert data data
    public int [] insertData (int [] array, int data) {
        // The new node on the end of the heap; array [array.length-1] = data
        int k = array.length-1; // nodes need to be adjusted
        int parent = (k-1) / 2; // parent node
        while (parent> = 0 && data> array [parent]) {
            array [k] = array [parent]; // parent node down
            k = parent;
            if (parent! = 0) {
                parent = (parent-1) / 2; // continue upward comparison
            } Else {// root node has been adjusted, out of the loop
                break;
            }
        }
        array [k] = data; // The node is inserted into the correct position
        return array;
    }

test:

public void toString (int [] array) {
        for (int i: array) {
            System.out.print (+ "");
        }
    }
    
    public static void main (String args []) {
        HeapSort hs = new HeapSort ();
        int [] array = {87,45,78,32,17,65,53,9,122};
        System.out.print ( "build large root heap:");
        hs.toString (hs.buildMaxHeap (array));
        System.out.print ( "\ n" + "delete the top of the stack elements:");
        hs.toString (hs.deleteMax (array));
        System.out.print ( "\ n" + "insert element 63:");
        hs.toString (hs.insertData (array, 63));
        System.out.print ( "\ n" + "large root heap sort:");
        hs.toString (hs.heapSort (array));
    }

Construction of large root heap 1: 122 877,845,176,553,932
2 Remove the top of the heap element: 874,578,321,765,539 -99999
3 Insert Element 63:87 637,845,176,553,932
4 large root heap sort: 9 1,732,455,363,657,887
     
         
       
         
  More:      
 
- Linux / UNIX: Use the dd command to create a 1GB size binary (Linux)
- CentOS6 5 source compiler installation Hadoop2.5.1 (Server)
- Android to determine whether the device to open WIFI, GPRS data connection (Programming)
- ACL permissions Linux command (Linux)
- Storm basic framework for analysis (Programming)
- Redhat 5 prohibit IPv6 (Linux)
- Android components save state series - Activity (Programming)
- HAProxy performance under high concurrency (Server)
- Installation Yarock 1.1.4 Music Player in Ubuntu (Linux)
- Linux ban single-user mode to enhance system security (Linux)
- Analysis of MySQL High Availability (Database)
- To install the iNode client on UbuntuKylin 13.10 (Linux)
- CentOS7 install JDK (Linux)
- IntelliJ IDEA run in Mac10.9 and JDK7 environment (Linux)
- Matters Oracle 11.2 single instance when connecting ASM need to pay attention and deal with the problem (Database)
- Linux memory Cache Analysis (Linux)
- TPCC-MySQL Benchmark (Database)
- Linux System Getting Started Learning: install software packages on Ubuntu and Fedora (Linux)
- Simple to use multi-threaded programming under Linux mutex and condition variable (Programming)
- Ubuntu 14.10 How to install office suite Calligra Suite 2.8.7 (Linux)
     
           
     
  CopyRight 2002-2016 newfreesoft.com, All Rights Reserved.