Home IT Linux Windows Database Network Programming Server Mobile  
           
  Home \ Programming \ Java implementation heap sort (large root heap)     - Ubuntu 14.10 / 14.04 / 12.04 How to install Kodi 14.0 RC3 (Linux)

- Deployment Kubernetes manage Docker example cluster on Ubuntu (Server)

- Awk include binding capacity larger than the specified size of all files directory (Linux)

- Introduction and bash history command to quickly call (Linux)

- OpenNMS separate database (Server)

- CentOS7 install and configure Nagios (Server)

- KVM virtualization of nested virtualization (Linux)

- Upgrade installation manual CentOS6.5 GCC4.8.2 (Linux)

- CentOS system dual network card IP information configuration (Linux)

- 14 useful example Linux Sort command (Linux)

- Debian users to install FFmpeg 2.2.2 (Linux)

- Ubuntu install perfectly handsome terminal Guake 0.8.1 (Linux)

- Python2 ---- function using dictionaries (Programming)

- By way of a binary installation innobackupex (Database)

- Fatal NI connect error 12170 error in Alert Log (Database)

- Monitoring network traffic with Iptraf in Linux environment (Linux)

- Linux Getting Started tutorial: build your own Vim (Linux)

- Installation configuration CUDA under Ubuntu 14.04 (Linux)

- Distributed File System using MogileFS (Linux)

- Android project using the command to create and install the package (Programming)

 
         
  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:      
 
- Installation and deployment of MariaDB under CentOS (Database)
- Nginx DHCP TFTP Kickstart set up automatic installation system (Server)
- JavaScript file loader LABjs API Explanation (Programming)
- Oracle inline view updates problems encountered (Database)
- Eclipse remove all comments and code spaces (Linux)
- CentOS installation Percona Server 5.5.42 compiling problem solve one case (Linux)
- How to use the on-screen keyboard in Linux (Linux)
- Getting Started with Linux: Learn how to install and access CentOS 7 Remote Desktop on a VPS (Server)
- Linux with Windows Explorer as a security system (Linux)
- Installation Docker FAQ on Ubuntu (Linux)
- ORA-38856: Unable instance UNNAMED_INSTANCE_2 (redo thread 2) marked enabled (Database)
- Linux server network penetration testing (Linux)
- Install and configure GO 1.2.1 under CentOS 6.5 (Linux)
- ADSL router to defend their own network security methods (Linux)
- Tecplot Installation under Linux (Linux)
- Use Visual Studio 2015 to develop Android program (Programming)
- Four Methods of Self - Learning Linux (Linux)
- JavaScript Advanced Programming notes event capture and event bubbling (Programming)
- Spring + Log4j + ActiveMQ remote logging - Analysis of combat (Server)
- Distributed File System using MogileFS (Linux)
     
           
     
  CopyRight 2002-2016 newfreesoft.com, All Rights Reserved.