Home IT Linux Windows Database Network Programming Server Mobile  
           
  Home \ Programming \ Java implementation heap sort (large root heap)     - HAProxy performance under high concurrency (Server)

- Java interview questions in nine radio (Programming)

- When should I use Angular 2 (Programming)

- Android recyclerview cardview (Programming)

- In-depth understanding of PHP ini configuration (Server)

- Vim plugin installation YouCompleteMe (Linux)

- LNMP summary of the issues common 502 Bad Gateway (Server)

- Linux common network tools: batch scanning of nmap hosting service (Linux)

- Ubuntu 15.10 How to install TeamViewer 11 (Linux)

- PPA on Ubuntu Linux installation Plank 0.8.0 (Linux)

- Redis is installed and set up Ubuntu 14.04 from the environment under the main ssdb (Server)

- Linux Network Analysis Tcpdump Command Guide (Linux)

- Nodejs mysql pool Example (Programming)

- Struts2 configure a static resource files without Struts processing (regular match) (Programming)

- Mount and unloading disks under Linux (Linux)

- sa weak passwords intrusion prevention (Linux)

- Github Remote Assistance (Linux)

- MySQL high availability cluster fragmentation of deployment uses Fabric (Database)

- Proxmox VE implement KVM OpenVZ virtualization cloud computing (Server)

- MySQL query plan key_len know all (Database)

 
         
  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:      
 
- CentOS 7 RHEL 7 to reset the root password (Linux)
- Ubuntu study notes and related problem solving (Linux)
- TPCC-MySQL Benchmark (Database)
- RCU lock in the evolution of the Linux kernel (Linux)
- Oracle how to maintain the consistency of read? (Database)
- WordPress blog installation Redis Cache (Server)
- The headers for the current running kernel were not found when VirtualBox installation enhancements (Linux)
- Installation and deployment of Hadoop 2.7.1 on Ubuntu 14.04 LTS (Server)
- ActionContext and ServletActionContext Summary (Programming)
- How to Install 3.16.7 CKT2 kernel in Ubuntu 14.10, Ubuntu 14.04 and its derivative versions (Linux)
- CentOS7 boot systemd introduction and use of management (Linux)
- OpenSSL: implementation creates a private CA, certificate signing request Explanation (Server)
- DataGuard a hardware issue warnings found (Database)
- Ubuntu / Fedora / CentOS system how to install Plex Media Server 0.9.9 (Linux)
- Kubernetes resolve application deployment model (Server)
- Stunning exclamation point at the Linux command line (Linux)
- Smooth upgrade to OpenSSH 6.7 Procedure (Linux)
- Linux environment has been running Tomcat how to deploy the new Tomcat (Server)
- How to build Mono 3.4.0 / 3.4.1 on Windows (Linux)
- Linux operating system to solve a serious fault handling (Linux)
     
           
     
  CopyRight 2002-2016 newfreesoft.com, All Rights Reserved.