Heap structure

  1. The heap structure is a complete binary tree structure implemented with arrays
  2. A complete binary tree is a large root heap if the maximum value of every subnumber is at the top
  3. A complete binary tree is a small root heap if the minimum of every subnumber is at the top
  4. HeapInsert and Heapify are the main heap structures
  5. The Java PriorityQueue structure is the heap structure

Think of the array as a complete binary tree structure, which for the array subscript I: left child: 2 x I + 1 Right child: 2 x I + 2 Parent node: (i-1) / 2

HeapInsert (add a new element to the heap) : heapSize keeps track of the number of elements in the heap, and also indicates where the new element should be placed. For each number given to the heap, heapSize++ is used to loop over the parent element and swap if it is larger than the parent element

The Heapify operation looks down from the INDEX position and sinks until my children are no longer older than me or have no children

Public class MyMaxHeap {/** * left child: 2 x I + 1 * Right child: 2 x I + 2 * Parent node: (i-1) / 2 */ private int[] heap; // heap size limit private final int limit; Private int heapSize; private int heapSize; public MyMaxHeap(int limit) { heap = new int[limit]; this.limit = limit; heapSize = 0; } public boolean isEmpty() { return heapSize == 0; } public boolean isFull() { return heapSize == limit; } public void push(int value) throws Exception { if (heapSize == limit) { throw new Exception("heap is full"); // heap[heapSize] = value; heapInsert(heap, heapSize++); } // Compare with the parent element, Private static void heapInsert(int[] arr, While (arr[index] > arr[((index - 1)/2)]) {if (arr[index] > arr[((index - 1)/2)) {if (arr[index] > arr[((index - 1)/2)) { swap(arr, index, ((index - 1)/2)); index = ((index - 1)/2); } } public static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; Public int pop() {int ans = heap[0]; // heap = heap[0]; // Swap heapSize (heap, 0, --heapSize) with heapSize (heap, 0, --heapSize); heapify(heap, 0, heapSize); return ans; } // Look down from index and sink // Until my children are no longer older than me, Private void heapify(int[] arr, int index, int heapSize) {int left = index * 2 + 1; While (left < heapSize) {// Which of the two children has the largest subscript? Int largest = left + 1 < heapSize && arr[left + 1] > arr[left]? left + 1 : left; Largest, largest = arr[largest] > arr[index]? largest : index; if (largest == index) { break; } swap(arr, largest, index); index = largest; left = index * 2 + 1; } } public static void heapSort(int[] arr) { if (arr == null || arr.length < 2) { return; } for (int i = 0; i < arr.length; i++) { heapInsert(arr, i); } int heapSize = arr.length; swap(arr, 0, --heapSize); while (heapSize > 0) { heapify(arr, 0, heapSize); swap(arr, 0, --heapSize); } } public static void main(String[] args) throws Exception { MyMaxHeap heap = new MyMaxHeap(7); heap.push(4); heap.push(3); heap.push(5); heap.push(7); heap.push(2); heap.push(1); while (! heap.isEmpty()) { System.out.println(heap.pop()); }}}Copy the code

The interview questions

I have an almost ordered array. Nearly ordered means that, if the array is sorted, each element moves no more than k, and k is small relative to the length of the array. Select an appropriate sorting strategy to sort this array.

public void sortedArrayDistanceLessK(int[] arr, int k) { PriorityQueue<Integer> heap = new PriorityQueue<>(); int index = 0; // add k+1 to the stack for (; index <= Math.min(arr.length - 1, k); index++) { heap.add(arr[index]); } int i = 0; for (; index < arr.length; i++, index++) { heap.add(arr[index]); Arr [I] = heap. Poll (); arr[I] = heap. } while (! heap.isEmpty()) { arr[i++] = heap.poll(); }}Copy the code