This is the seventh day of my participation in the August Challenge. For details, see:August is more challenging

The heap

A heap is a special kind of tree — a binary tree implemented using an array

  1. Complete binary tree (all layers are full except the last, and leaf nodes are sorted from left)
  2. Each node in the heap has a value greater than or equal to the value of its left and right children.

Each node’s value is greater than or equal to the heap of each node’s value in the subtree, which is called the “big top heap.” A heap where each node’s value is less than or equal to the value of each node in the subtree is called a “small top heap.”

Implementations of the heap are usually done with arrays, because instead of using Pointers, you just need to know the array index to locate the corresponding element

As can be seen from the figure, the left child node of the node with the subscript I in the array is the node with the subscript I ∗2, the right child node is the node with the subscript I ∗2+1, and the parent node is the node with the subscript I /2s.

The difference between heap and ordinary binary tree

  1. In a binary tree, the left node < the parent node < the right node, and the heap only needs to satisfy that the root node is larger or smaller than all the child nodes
  2. The memory footprint of the heap is lower than that of a normal binary tree because there is no need to store pointer information about the nodes involved

Stack operation

Insert an element at the end of the array

Inserting an element into an array is as simple as inserting it directly into the end of the array, but ensuring the integrity of the heap (the two features mentioned above) requires a certain amount of workThe heap,Operation.

How heapization works: It can be easily implemented by focusing on the second feature of the heap mentioned aboveFrom the new node, the parent and child nodes are switched until the above relationship is met

The implementation code


public class Heap {
  private int[] a; // An array that stores data starting with index 1
  private int n;  // Maximum number of data that can be stored in the heap
  private int count; // The number of data already stored in the heap

  public Heap(int capacity) {
    a = new int[capacity + 1];
    n = capacity;
    count = 0;
  }

  public void insert(int data) {
    if (count >= n) return; / / is filled with
    ++count;
    a[count] = data;
    int i = count;
    while (i/2 > 0 && a[i] > a[i/2]) { // Stack from bottom to top
      swap(a, i, i/2); // The swap() function swaps two elements with subscripts I and I /2
      i = i/2; }}}Copy the code

Remove the top element of the heap

  • Remove the top element of the heap
  • Place the last node at the top of the heap element to be removed (why do I do this? Because there is no way to determine where the pit will end up. I can’t form a complete binary tree.)
  • And then we heap it

Code implementation


public void removeMax(a) {
  if (count == 0) return -1; // There is no data in the heap
  a[1] = a[count];
  --count;
  heapify(a, count, 1);
}

private void heapify(int[] a, int n, int i) { // Heap from top to bottom
  while (true) {
    int maxPos = i;
    if (i*2 <= n && a[i] < a[i*2]) maxPos = i*2;
    if (i*2+1 <= n && a[maxPos] < a[i*2+1]) maxPos = i*2+1;
    if (maxPos == i) break; swap(a, i, maxPos); i = maxPos; }}Copy the code

Heap sort

Building the heap

So there are two ways to do that

First: the default heap is only one element, and then according to the above insert operation, has been added to the last element, and finally through the heap operation to achieve the heap

Second: Start with the last non-leaf node, compare it to its children, replace it with the largest node, and then move the pointer forward (i.e. get the penultimate non-leaf node). The last non-leaf node is compared because the leaf node is no longer comparable (no child nodes)

private static void buildHeap(int[] a, int n) {
  for (int i = n/2; i >= 1; --i) { heapify(a, n, i); }}private static void heapify(int[] a, int n, int i) {
  while (true) {
    int maxPos = i;
    if (i*2 <= n && a[i] < a[i*2]) maxPos = i*2;
    if (i*2+1 <= n && a[maxPos] < a[i*2+1]) maxPos = i*2+1;
    if (maxPos == i) break; swap(a, i, maxPos); i = maxPos; }}Copy the code

The time complexity of the heap sorting process is O(n).

The sorting

After the pile is built, the big top pile is formed.

  1. Remove the heap-top element (place the heap-fixed element at the end of the array, and place the last element at the top of the heap), and then heapize
  2. Continue to perform the preceding operations

The whole heap sort process, all only need very individual temporary storage space, so heap sort is in place algorithm. Heapsort consists of two operations: heapsort and heapsort. Heapsort takes O(n) time and sorting takes O(nlogn) time, so heapsort as a whole takes O(nlogn) time.