The heap is logically a complete binary tree, so it can be stored in arrays, while the rest of the tree is mostly chained

  • Heap sort:
    • Big Top heap: A big top heap is a heap that has the largest parent in any tree
    • Small top heap: A small top heap is the smallest parent in any tree
  • There are two operations on the heap:
    • Float up: Generally used to balance the heap after adding new elements to the heap
    • Sink: Generally used to balance the heap after removing the top of the heap and replacing the tail of the heap to the top
  • Heap sort: use the characteristics of the big top heap and the small top heap, keep taking out the top of the heap, take out the maximum value of the elements in the heap, and then balance the heap

The following article uses the big top heap as an example to implement various operations of the heap with Java.

1.MaxHeap

Large Top heap: The largest top of any heap

Comparable ensures that all nodes are Comparable and are heaps based
public class MaxHeap <E extends Comparable<E>> {
	// Complete binary tree, arranged neatly (equivalent to layer by layer), can use array storage
    private ArrayList<E> data;

    public MaxHeap(int capcity) {
        data = new ArrayList<>(capcity);
    }

    public MaxHeap(a) {
        data = new ArrayList<>();
    }

    // Whether the heap is empty
    public boolean isEmpty(a) {
        return data.isEmpty();
    }
    // Number of elements in the heap
    public int size(a) {
        return this.data.size();
    }
	
	/ /...
}
Copy the code

2. Operation 1: Obtain the parent node or child node

parent()

// Returns the parent node of the idX location element
Parent = (i-1) /2; parent = (i-1) /2;
private int parent(int idx) {
    if (idx == 0) {
        throw new IllegalArgumentException("index-0 doesn't have parent");
    }
    return (idx - 1) / 2;
}
Copy the code

leftChild() / rightChild()

// Returns the child node of the idX position element
// Note: this is set from 0
private int leftChild(int idx) {
    // If set from 1, leftChild = idx * 2
    return idx * 2 + 1;
}
private int rightChild(int idx) {
    // rightChild= idx * 2 + 1
    return idx * 2 + 2;
}
Copy the code

2. Operation 2: Add elements

add()

  1. Put the element at the end of the heap, the last element in the array
  2. Join us at the end. Float up
public void add(E e) {
    data.add(e);
    // Pass in the index that needs to float
    siftUp(data.size() - 1);
}
Copy the code

siftUp()

  • Float up: Child nodes swap with their (smaller) parent nodes
  • Time: O (logn), get parent is continuously divided (/2)
private void siftUp(int k) {
    // Swap as long as the parent (data[parent]) is smaller than the child (data[k])
    while (k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0) {
        // 1. Swap positions in the array
        // Note: this is true
        Collections.swap(k, parent(k));
        // 2. Update the child node for the next float
        // Note: Data. set can also be used for three stepsk = parent(k); }}Copy the code

3. Operation 3: Fetch the top (largest element)

extractMax()

Remove the pile top

  1. Get the top element of the heap
  2. Delete the pile top
    1. Swap the top of the heap (0) with the bottom of the heap (size-1) because a new top is generated
    2. Delete the pile end
    3. Sinking pile top
public E extractMax(a) {
    // 1. Get the top element
    E ret = findMax() ;
    
	// 2.1 Change the top of the heap to the bottom of the heap
    Collections.swap(0, data.size() - 1);
    // 2.2 Delete heap tails
    data.remove(data.size() - 1);
	// 2.3 Sinking pile top
    siftDown(0) :return ret;
}
Copy the code

findMax()

Gets the largest element in the heap

public E findMax(a) {
    if (data.size() == 0) {
        throw new IllegalArgumentException("Can not findMax when heap is empty");
    }
    // Max = first element of array (0)
    return data.get(0);
}
Copy the code

siftDown()

  • Heap sink: Swaps with nodes with larger values (and larger than itself) of the left and right child nodes
  • Time: O (logn), get Child is continuously divided (/2)
private void siftDown(int k) {
    1. Check whether the current node has child nodes. You go down to the leaf, you have no sons, you don't have to go down
    // Note: Since the leftChild index must be smaller than rightChild, any leftChild has children
    while (leftChild(k) < data.size()) {
        // 2. Get the values of leftChild and rightChild
        int j = leftChild(k);
        if (j + 1 < data.size() && data.get(j + 1).compareTo(data.get(j)) > 0) {
            j = rightChild(k);
        }
		
        // 3. Check whether the child node is larger than itself (parent node)
        if (data.get(k).compareTo(data.get(j)) >= 0) {
            break;
        }
		
        // 4. If greater than, swap the two node positions in the array
        Collections.swap(k, j);
        
        // Update the parent node for the next sinkk = j; }}Copy the code

4. Operation 4: Array construct heap

  • ====> Time = O (n*logn)
  • ====> Time = O (n)
// The array to construct the heap is passed in
public MaxHeap(E[] arr) {
    // Note: The array cannot be used directly as an ArrayList argument
    data = new ArrayList<>(Arrays.asList(arr));
    // The parent of the last leaf (leng-1) is (i-1) / 2.
    for (int i = parent(arr.length - 1); i >= 0; i--) {
        // Sink one by onesiftDown(i); }}Copy the code

=> Verify the maximum heap

Before we look at heap sorting, let’s verify that we’ve written the right code. Add a million random numbers to the heap, then top them off and put them into an array, then check to see if they are sorted from largest to smallest:

public class Test {

    public static void main(String[] args) {
        int n = 10000000;

        MaxHeap<Integer> heap = new MaxHeap<>();
        Random random = new Random();
        // 1. Add a million random numbers to the heap
        for (int i = 0; i < n; i++)
            heap.add(random.nextInt(Integer.MAX_VALUE));

        // 2. Keep removing the top of the heap from the largest heap --> from the largest to the smallest
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = heap.extractMax();
        }
		
        // 3. Verify that the retrieved elements are sorted from largest to smallest
        for (int i = 0; i < n - 1; i++)
            if (arr[i] < arr[i + 1])
                throw  new IllegalArgumentException("Error");

        System.out.println("Test MaxHeap Success!"); }}Copy the code

You could have just created an array, made it the largest heap, and kept taking the top. I’m sure you’ve seen the ability of the heap to sort through the examples above.

= = > heap sort

Heap sort principle: in short, it is to take advantage of the characteristics of the big top heap and the small top heap, keep taking out the top (the maximum value of the elements in the heap), and then balance the heap.

  1. Build maximum heap: Using the heap-building idea above, start sinking from the last node that is not a leaf node
  2. Fetch top: Not really fetch, but swap the top of the heap (arr[0]) to the tail (arr[I]) to achieve the top of the heap ==> the top of the heap is sorted from small to large
  3. New heap rebalancing: Since the previous step changed the bottom of the heap to the top of the heap, just sink it again

Parent = IDx / 2, leftChild = IDx * 2, rightChild = IDx * 2 + 1

public class HeapSort {

    public void sort(int[] arr) {
        int length = arr.length;
		
		// 1. Build the maximum heap: sink from the last node that is not a leaf node
		// I =(length-1)/2, which means to obtain the father of the last leaf node, that is, the last node that is not a leaf node
        for (int i = (length - 1) / 2; i >= 0; i--) {
            siftDown(arr,length, i);
        }
		
        for (int i = length - 1; i > 0; i--) {
        	// 2. Remove the top of the heap: Swap the top of the heap (ARr [0]) to the tail (ARr [I]) to achieve the top of the heap
            swap(arr, 0, i);
            // 3. New heap rebalancing: The previous step has shifted the bottom of the heap to the top of the heap, so just sink it again
            // The length of the new heap is now 1 less than before.
            siftDown(arr, i, 0); }}private void siftDown(int[] arr, int length, int idx) {
    	// If you sink to the leaf, you have no son
    	// use leftChild (2*idx), because if the leftChild exceeds length, the right child must also exceed length
        while (2 * idx < length) {
        	
        	// Decide which son is bigger, the left son or the right son
            int j = 2 * idx;
            if (j + 1 < length && arr[j+1] > arr[j])
                j++; // if the right son is big, j++ is used
			
			// Determine whether the father is older than the son
            if (arr[idx] >= arr[j])
                break;
			
			// The father is smaller than the son
            swap(arr, idx, j);
            // Update the parent IDX, proceed to the next subtree to determine the sinkidx = j; }}private void swap(int[] arr, int idx1, int idx2) {
        intt = arr[idx1]; arr[idx1] = arr[idx2]; arr[idx2] = t; }}Copy the code

In addition, if you are interested in other kinds of sorting, you can refer to this article to illustrate ten sorting algorithms and Java implementation (detailed)…

5. Operation 5: Take out the top of the heap and add another element

  • ====> 2 * O (logn)
  • ====> O (logn)

replace()

public E replace(E e) {
        // 1. Get the top element
        E ret = findMax();
    	// 2. Modify the top of the heap, i.e. the position of array 0
        data.set(0, e);
        / / 3. The sink
        siftDown(0);
    
        return ret;
}
Copy the code

The complete code

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class MaxHeap <E extends Comparable<E>> {

    private ArrayList<E> data;

    public MaxHeap(int capcity) {
        data = new ArrayList<>(capcity);
    }

    public MaxHeap(a) {
        data = new ArrayList<>();
    }

    public MaxHeap(E[] arr) {
        data = new ArrayList<>(Arrays.asList(arr));
        for (int i = parent(arr.length - 1); i >= 0; i--) { siftUp(i); }}// Whether the heap is empty
    public boolean isEmpty(a) {
        return data.isEmpty();
    }
    // Number of elements in the heap
    public int size(a) {
        return this.data.size();
    }

    // Returns the parent node of the idX location element
    Parent = (i-1) /2; parent = (i-1) /2;
    private int parent(int idx) {
        if (idx == 0) {
            throw new IllegalArgumentException("index-0 doesn't have parent");
        }
        return (idx - 1) / 2;
    }

    // Returns the child node of the idX position element
    // Note: this is set from 0
    private int leftChild(int idx) {
        // If set from 1, leftChild = idx * 2
        return idx * 2 + 1;
    }
    private int rightChild(int idx) {
        // If set from 1, leftChild = idx * 2
        return idx * 2 + 2;
    }

    // Add elements
    public void add(E e) {
        data.add(e);
        siftUp(data.size() - 1);
    }

    private void siftUp(int k) {
        while (k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0) { Collections.swap(data, k, parent(k)); k = parent(k); }}// Get the largest element in the heap
    public E findMax(a) {
        if (data.size() == 0) {
            throw new IllegalArgumentException("Can not findMax when heap is empty");
        }
        // The heap top is the largest,
        return data.get(0);
    }

    public E extractMax(a) {
        E ret = findMax() ;

        Collections.swap(data, 0, data.size() - 1);
        data.remove(data.size() - 1);

        siftDown(0);
        return ret;
    }

    private void siftDown(int k) {
        while (leftChild(k) < data.size()) {
            int j = leftChild(k);
            if (j + 1 < data.size() && data.get(j + 1).compareTo(data.get(j)) > 0) {
                j = rightChild(k);
            }

            if (data.get(k).compareTo(data.get(j)) >= 0) {
                break; } Collections.swap(data, k, j); k = j; }}public E replace(E e) {
        E ret = findMax();
        data.set(0, e);
        siftDown(0);
        returnret; }}Copy the code

Finally, if you are interested in the application of the heap in Java, take a look at the source code of PriorityQueue, which is implemented through the small top heap, here put a portal [Java collection source] PriorityQueue source analysis.