HEAPSORT and comparer

Heap structure ：

（1） Logically, conceptually ： Perfect binary tree （ A full binary tree or a binary tree that becomes full from left to right ）

（2） Storage represents ： Array from 0 The starting continuous segment represents a complete binary tree , Use size Describe how many nodes the tree has , stay i Node on location , Its left subscript is （2*i+1）, The right child subscript is （2*i+2）, Parent node is （i-1）/2.

（3） classification ：

Big root pile ： The top of the heap is the largest element of the whole heap , Similarly, each subtree also satisfies that the maximum value of the subtree is the value of the head node

Heap ： The top of the heap is the smallest element of the whole heap , Similarly, each subtree also satisfies that the minimum value of the subtree is the value of the head node

Two important processes ：

heapinsert： Compare the adjustment process with the parent node

 /*
     The process of ascending from the bottom of a pile 
     A number in arr Of index Location , Through this method, find the location of the large root heap where it should be 
     Method ： Find the parent node up in turn , Until the parent node is larger than this number 
     */
    public static void heapinsert(int[] arr, int index){
        while(arr[index] > arr[(index - 1)/2]){// contain index stay 0 Location 
            swap(arr, index, (index-1)/2);
            index = (index - 1) / 2;
        }
    }

heapify： Compare the adjustment process with the child nodes

 /*
     A number in index Location , Can you sink down and find the right place 
     Large root heap method ： Maximum exchange with left and right children , Compare with the following children in turn 
     */
    public static void heapify(int[] arr, int index, int heapSize){
        int left = index * 2 + 1; // Left child's subscript 
        while(left < heapSize){ // If you have children 
            // If there is a right child , Find the larger subscript in the left and right children 
            int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
            // Compare your older child to yourself , Take the larger 
            largest = arr[index] >= arr[largest] ? index : largest;
            if(index == largest) break;// If you are older than your child , Then stop sinking 
            swap(arr, index, largest);// Otherwise exchange , Continue to compare 
            index = largest;
            left = index * 2 + 1;
        }
    }

Heap sort （ From small to large —— Big root pile ） Time and again ：O(N*logN), Empty recovery ：O(1)

First form a pile , Then pop the elements from the top of the heap , Put the array from back to front .

When a heap is formed ：

Law 1： Start at the front of the array , Add elements to the heap in turn to build the heap

Law 2： Suppose that all the elements have formed a heap tree , Then sink from back to front , First, adjust the local small pile , Adjusting a lot . The last floor is about N/2 Nodes , Each node handles 1 Time （ Take a look at ）; The penultimate floor is about N/4 Nodes , Each node handles 2 Time （ see 1 eye , May move down 1 Step ）.... The sum of all operations is the total number of operations （ type 1）. Multiply this equation by 2（ type 2）, Offset and subtract the two formulas , The final time complexity is O(N).

 // Order from small to large 
    public static void heapSortMax(int[] arr){
        if(arr == null || arr.length < 2) return;
        int heapSize = 0;

        // Let the array form a large root heap , Law 1：O(N*logN)
//        for(int i = 0; i < arr.length; i++){// Form a large root pile   O(N)
//            heapinsert(arr, i); //O(logN)
//        }

        // Let the array form a large root heap , Law 2：O(N)
        for(int i = arr.length - 1; i >= 0; i--){
            heapify(arr, i, arr.length);// The third parameter here is the size of the heap , Because it sinks in reverse order , So take the maximum 
        }
        // The top elements of the large root heap pop up in turn 
        heapSize = arr.length;
        swap(arr, 0, --heapSize);// If you will swap after heapify All written to the loop , Just one more meaningless heapify
        while (heapSize > 0 ){//O(N)
            heapify(arr, 0, heapSize);// need  len-1  Time heapify that will do .O(logN)
            swap(arr, 0, --heapSize);//O(1)
        }
    }

  From big to small （ Heap ）,Java The default priority queue in the system is the small root heap

 // Heap 
    public static void heapnsert_min(int[] arr, int index){
        while (arr[index] < arr[(index - 1) / 2]){
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    public static void heapify_min(int[] arr, int index, int heapSize){
        int left = index * 2 + 1;
        while (left < heapSize){
            // Note that the right child can only be selected if the conditions are met , Otherwise, if it is else Take the right child , There are also cases where the right child does not exist , Will cross the border 
            int less = (left+1 < heapSize) && arr[left + 1] < arr[left] ? left + 1 : left;
            less = arr[less] < arr[index] ? less : index;
            if(less == index) break;
            swap(arr, less, index);
            index = less;
            left = index * 2 + 1;
        }
    }
    // Sort from large to small 
    public static void heapSortMin(int[] arr){
        // Build small root pile 
        for(int i = arr.length - 1; i >= 0; i--){
            heapify_min(arr, i, arr.length);
        }
        // Eject from the top of the stack one by one 
        int heapSize = arr.length;
        swap(arr, 0, --heapSize);
        while (heapSize > 0){
            heapify_min(arr, 0, heapSize);
            swap(arr, 0, --heapSize);
        }
    }

Example ： 

/**
 *  Heap sort extension problem 
 * Problem description ：  We know an almost ordered array , Almost orderly means , If you put the array in order ,
 *  Each element does not move more than k, also k Small relative to arrays ,
 *  Please select an appropriate sorting algorithm to sort the data .
 *  Use structure ： Priority queue （ Heap ）
 *  Time and again ：O（N*logK）
 * @param arr
 * @param k
 */

solve ： Use the default priority queue  PriorityQueue Before the （k+1） Create a small root heap with three elements , The elements at the top of the heap must be placed in arr[0] The location of , In turn, add new elements backward to build a new small root heap , Put the pop-up element in arr[1] The location of , Until the end of the entire array （k+1） All the elements are in the heap , Then pop it up from small to large and put it into the array . The time complexity is O(N*logK)

If you consider the expansion of the heap , It's a multiple expansion , That is, expansion logN Time , Copy the original elements after each expansion , That is, the cost of a single expansion is O（N）, So the total number of operations is O(N*logN), The expansion cost shared by each element is O[(N*logN)/N] = O(logN)

 public static void sortedArrDistanceLessK(int[] arr, int k){
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        int index = 0;
        for(; index < Math.min(k, arr.length); index++){// The former （k+1） Put them in the small root pile 
            heap.add(arr[index]);
        }
        int i = 0;
        for(; index < arr.length; index++, i++){// Pop up a , Add one , Until you've added 
            arr[i] = heap.poll();// The top of the heap is ejected and put into k The first position under the range 
            heap.add(arr[index]);//k The whole range moves back 
        }
        while (!heap.isEmpty()){// The remaining elements in the heap are ejected sequentially 
            arr[i++] = heap.poll();
        }
    }

Be careful ：

The priority queue given by the system （ Heap structure ） The difference with your own handwriting pile ： When the system heap structure is initially built, the size of structural elements has been fixed , If you want to change a certain number and readjust it into a heap , You may need to rescan all elements ,heapify and heapinsert, There is a high price , At this point, you need to write a stack of handwriting , It is necessary to directly judge the number of changes heapify still heapinsert. If you simply need to add and pop up numbers , You can use the system heap , It involves changing the heap elements , Handwriting required

The comparator ：

（1） The essence ： Overloading comparison operators

（2） It can be well applied to special sorting rules

（3） It can be well applied to the structure sorted according to special standards

Implementation method ： Write a comparator class to implement Comparator< Classes to compare > Interface , again compare

！！！ The rules ：

  stay Arrays.sort()、 PriorityQueue、TreeSet The comparator object can be passed in , Establish... According to the given requirements . In the heap , The first number in the comparator should be placed on top , In this way, the default small root heap can also be changed to a large root heap