Home IT Linux Windows Database Network Programming Server Mobile  
           
  Home \ Programming \ Java implementation heap sort (large root heap)     - Samhain: Powerful intrusion detection system under Linux (Linux)

- Circular list of Java programming (Programming)

- How to install Ubuntu California - the calendar application (Linux)

- Oracle Database Performance Optimization of memory disk (Database)

- Computer security perimeter recommendations (Linux)

- MySQL stored procedures and triggers (Database)

- 30 Practical Linux system administrators will learn the command (Linux)

- Quick paging ROW_NUMBER conducted (Database)

- Use netcat [nc] command on Linux and Unix port scan (Server)

- MySQL Server Time Synchronization Problem (Database)

- Simple RPM package production (Linux)

- CentOS 6.6 install JDK7 (Linux)

- Ubuntu 14.04 Fixed update information is outdated error (Linux)

- Xmanager Remote Desktop connection CentOS (Linux)

- Spring WebSocket Comments (Programming)

- Ubuntu system safe and caution sudo su command (Linux)

- Oracle table space usage monitoring (Database)

- KVM virtualization nested configuration (Server)

- Use LKM change the default linux security level (Linux)

- Actual SSH port forwarding (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:      
 
- Function Getting the Linux shell (Programming)
- RedHat Linux 5.5 installation process SVN Service Notes (Server)
- Linux-- sub-volume compression and decompression (Linux)
- Linux system - The understanding cpu load (Linux)
- Android HTTP request with Get Information (Programming)
- Ubuntu in Vim editor display processing method Chinese garbled (Linux)
- Ubuntu prompt / lack of boot space solutions (Linux)
- ElasticSearch basic usage and cluster structures (Server)
- Oracle index visible and hidden (visible / invisible) (Database)
- C ++ handling text input (Programming)
- Ubuntu 14.04 Nvidia graphics driver installation and settings (Linux)
- Ubuntu 14.10 Server configuration wireless Internet access (Server)
- Linux atomic operations and synchronization mechanisms (Programming)
- Batch kill processes using awk command (Linux)
- Linux System Getting Started Learning: Using the Linux command line detected DVD burner name and write speeds (Linux)
- MacBook Air install Ubuntu dual system (Linux)
- Build your own Git server under Linux (Server)
- C language macro definition #define Usage (Programming)
- Linux dd command make U disk boot disk (Linux)
- Node.js developers must know four JavaScript concepts (Programming)
     
           
     
  CopyRight 2002-2016 newfreesoft.com, All Rights Reserved.