Merge sort doesn’t use recursion

  • Use a variable that increments by 1, 2, 4, 8 to control the merging of elements 1, 2, 4, and so on on the left and right sides

Complete binary tree

  • A complete binary tree is either full, or leaves appear at the bottom of the tree, and as soon as leaves appear, leaves follow
  • Complete binary trees can be represented by array subscripts ranging from 0 to 7, with left, right, and parent nodes calculated according to the following formula
  • For any node I
  • Left node 2 * I + 1
  • I + 2 * 2 right node
  • The parent node (I – 1) / 2

The heap

Heap (complete binary tree)

Big root pile

  • In a perfect binary tree, the maximum value of each subtree is the head node

Small root pile

  • In a complete binary tree, the minimum value of each subtree is the head node

Heap insert and delete operations are O(logn), heap build operations are O(n)

Instead of chain storage, the heap is stored sequentially. The left child index is 2*parent +1; The right child subscript is 2 * parent+2

Priority queue: Such as maximum priority queue, let the largest element out, even if the largest element is not at the head of the queue, it is still the first out, because it has the highest priority. The bottom layer of the priority queue is implemented using a large root heap. Each queue operation is an insert operation to the heap, and each queue operation is a deletion of the heap vertex

Since the time complexity of both the rise and fall of the binary heap is O(logn), the time complexity of the priority queue is also O(logn).

example

​

  • Add elements: Add elements to an array with subscripts from 0 to 7 in the order of input. If no array is added, the parent node is evaluated by (i-1) / 2, and then compared with the parent node. If the parent node is larger than the parent node, the parent node is swapped. For each element added, heapsize+1. Heapsize specifies the size of the heap.
  • Return maximum value: Swap the top and bottom elements of the large root heap, and return the top value of heapsize-1. After the last element moves to the top, it needs to find its left and right child nodes, compare them, and swap if there are children older than it. And so on.
  • Array expansion: If the original allocation is only one byte, dynamically add elements to the array expansion. So you need log (N) expansion, and then you need to copy N numbers into the array after expansion; So the cost is N log of N, and if you average it, the cost is log of N.

The complete code

  • The heapsort method is used to insert elements into an array, one by one

  • Heapify works by placing the smallest element at the top to see if it drops if you pop it up

  • I don’t really know what this code means

    package class02;

    import java.util.Arrays; import java.util.PriorityQueue;

    public class Code03_HeapSort {

    public static void heapSort(int[] arr) { if (arr == null || arr.length < 2) { return; } for (int i = 0; i < arr.length; i++) { // O(N) heapInsert(arr, i); // O(logN) } // for(int i = arr.length -1; i >=0; i--) { // heapify(arr, i, arr.length); // } int heapSize = arr.length; swap(arr, 0, --heapSize); while (heapSize > 0) { // O(N) heapify(arr, 0, heapSize); // O(logN) swap(arr, 0, --heapSize); // arr[0... index-1]; // arr[0... index-1]; Public static void heapInsert(int[] arr, int index) {while (arr[] > arr[(index - 1) / 2]) {swap(arr, index, (index - 1) / 2); index = (index - 1) / 2; }} public static void heapify(int[] arr, int heapSize) {int left = index * 2 + 1; While (left < heapSize) {while (left < heapSize) {while (left < heapSize) { Largest int largest = left + 1 < heapSize && arr[left + 1] > arr[left]? left + 1 : left; Largest = arr[largest] > arr[index] largest : index; if (largest == index) { break; } swap(arr, largest, index); index = largest; left = index * 2 + 1; } } public static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } // for test public static void comparator(int[] arr) { Arrays.sort(arr); } // for test public static int[] generateRandomArray(int maxSize, int maxValue) { int[] arr = new int[(int) ((maxSize + 1) * Math.random())]; for (int i = 0; i < arr.length; i++) { arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random()); } return arr; } // for test public static int[] copyArray(int[] arr) { if (arr == null) { return null; } int[] res = new int[arr.length]; for (int i = 0; i < arr.length; i++) { res[i] = arr[i]; } return res; } // for test public static boolean isEqual(int[] arr1, int[] arr2) { if ((arr1 == null && arr2 ! = null) || (arr1 ! = null && arr2 == null)) { return false; } if (arr1 == null && arr2 == null) { return true; } if (arr1.length ! = arr2.length) { return false; } for (int i = 0; i < arr1.length; i++) { if (arr1[i] ! = arr2[i]) { return false; } } return true; } // for test public static void printArray(int[] arr) { if (arr == null) { return; } for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); } // for test public static void main(String[] args) { int index = -1; System.out.println(index / 2); int testTime = 500000; int maxSize = 100; int maxValue = 100; boolean succeed = true; for (int i = 0; i < testTime; i++) { int[] arr1 = generateRandomArray(maxSize, maxValue); int[] arr2 = copyArray(arr1); heapSort(arr1); comparator(arr2); if (! isEqual(arr1, arr2)) { succeed = false; break; } } System.out.println(succeed ? "Nice!" : "Fucking fucked!" ); int[] arr = generateRandomArray(maxSize, maxValue); printArray(arr); heapSort(arr); printArray(arr); }Copy the code

    }

Use of comparators

  • Essence: Overloaded comparison operator
  • Comparators can be used for sorting by special criteria
  • Comparators can be applied to special standard sort structures
  • Defining your own comparison rules is similar to C++ symbol overloading, such as defining a student structure that contains the student’s name, age, and id. By comparing the ages of the structures, the order is carried out

Extension of heap sort

  • You have an almost ordered array, and almost ordered means that if you put the array in order, each element moves no more than k, and k is small relative to the array. Please select an appropriate sorting algorithm to sort this data
  • Create a small root heap (k+1), place k+1 elements in the requested memory space, and adjust them each time. The element at position 0 is the smallest element; Then eject the 0 element, and insert the new element into the applied space to adjust. Insert a new element every time the first element pops up, adjust the whole thing.

​