The binary structure of the data structure

What is a binary heap?

二叉堆In essence, it is a 二叉树, and according to the different root node data, it is divided into: 最大堆 And 最小堆

What is the biggest heap? The value of the parent node Forever greater than or equal to The value of two 孩子 Node.

       

What is the smallest heap? The value of the parent node Forever is less than or equal to The value of two 孩子 Node.

The characteristics of the binary fork

自调: When inserting or deleting data, the binary heap will change the position of the element so that the parent node is still greater than (less than) the child node.

完全二叉树: The binary fork is a complete binary tree.

二叉堆 Add and remove elements

Add element: The elemental insertion of the binary fork is always inserted into the last position of the binary tree, taking the smallest heap example. If you insert a new element 0.

0 is compared with parent node 5, which is smaller than the parent node, so 0 is floating, that is, 0 and parent node 5 exchange positions.

is still compared with the parent node, the parent node is 3, 0 is less than 3, then 0 continues to float, 0 and 3 exchange positions.

The parent node is now 1,0 is still smaller than the parent node 1, and floats up to the root node position, and the comparison ends.

删除元素: The deletion of the binary heap element always deletes the elements at the top of the heap. The largest heap is the maximum value in the heap, and the smallest is the opposite. If we want to delete the top element of the heap 1.

In order to maintain the balance of the binary stack, the last element 10 is placed on the top of the heap. Now it is a complete binary tree, but the balance of the binary heap has been destroyed, so let Element 10 sinks to a suitable position.

Let element 10 compare with two child nodes, take the smallest child node, exchange position, child node 3, 2, 2 is the smallest, so exchange position with 2.

At this time, the two child nodes of the 10 are respectively 7, 8 , so continue to sink, and exchange positions with 7.

10 is already a leaf node, and the sinking is over. At this point, the binary heap has been restored.

码 实现

二叉堆 Although it is a complete binary tree, it is not stored in a chain structure. Due to the nature of the complete binary tree, it can be stored in an array.

But how do you locate the child node from the current element? We can use the index to calculate.

Element 1 is stored in the first position, the index is 0, then the index of the index of his left child node is parent * 2 + 1 = 1, and the index of the index of the right child node is parent * 2 + 2 = 2; but if we define the index of the first element as 1 , then the index of the left child's index is parent * 2 = 2, and the index of the right child's index is parent * 2 + 1 = 3.

Get this clear and start writing code

Package com.zjm.binheap;

/**
 * Maximum heap implementation
 * @author Zhao JinMing
 * @data 2018.9.15
 * @version 0.9.0
 */
Public class BinaryHeap {
    Private int elementCount;

    Private int[] elements;

    Private static final int DEFAULT_CAPACITY = 16;

    Private static final int MAXIMUM_CAPACITY = 1 << 30;

    Public BinaryHeap() {
        This(DEFAULT_CAPACITY);
    }

    Public BinaryHeap(int[] data) {
        This();
        For (int d : data) {
            Push(d);
        }
    }

    Public BinaryHeap(int capacity) {
        Elements = new int[tableSizeFor(capacity)];
        elementCount = 0;
    }

    /**
     * Enrollment operation
     * @param data enqueue data
     */
    Public void push(int data) {
        If(elements.length - 1 == elementCount)
            Resize((elementCount + 1) << 1);
        Elements[++elementCount] = data;
        floatElement(elementCount);

    }

    /**
     * Pop-up queue
     * @return returns the maximum or minimum value of the queue
     */
    Public int pop() {
        If(elements.length < elementCount >> 2)
            Resize(elementCount >> 2);
        Int res = elements[1];
        Swap(1, elementCount);
        Elements[elementCount--] = 0;
        sinkElement();
        Return res;
    }

    /**
     * View team leader
     * @return returns the first element of the queue
     */
    Public int peek() {
        Return elementCount == 0 ? -1 : elements[1];
    }

    /**
     * Number of elements
     * @return returns the number of elements
     */
    Public int size() {
        Return elementCount;
    }

    /**
     * Inspection is not empty
     * @return TRUE queue is empty
     */
    Public boolean isEmpty() {
        Return elementCount == 0;
    }

    /**
     * Reset the element size
     * @param size size of the new array
     */
    Private void resize(int size) {
        If (size > MAXIMUM_CAPACITY) {
            //TODO
        }
        Int[] newElements = new int[size];
        copyArray(elements, newElements);
        Elements = newElements;
    }

    /**
     * Element floats
     * @param index Floating element index position
     */
    Private void floatElement(int index) {
        While (index > 1 && elements[index >> 1] < elements[index]) {
            Swap(index >> 1, index);
            Index >>= 1;
        }
    }

    /**
     * Element sinking
     */
    Private void sinkElement() {
        Int index = 1;
        While (index << 1 <= elementCount &&
                (elements[index] < elements[index << 1] || elements[index] < elements[(index << 1) + 1])) {
            Int p = index << 1;
            Int i = elements[p] > elements[p + 1] ? p : p + 1;
            Swap(index, i);
            Index = (i & 0x01) == 1 ? (index << 1) + 1 : index << 1;
        }
    }

    /**
     * The method in HashMap, the incoming parameter becomes the next 1 << n (2 n power is greater than cap and 2 n-1 power is less than cap)
     * @param cap changed parameters
     * @return 1 << n
     */
    Private static int tableSizeFor(int cap) {
        Int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        Return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

    /**
     * Array copy
     * @param source The source array being copied
     * @param target copy target array
     */
    Private static void copyArray(int[] source, int[] target) {
        System.arraycopy(source, 0, target, 0, source.length);
    }

    /**
     * Swap array two element positions
     * @param indexA index position of element A
     * @param indexB index position of element B
     */
    Private void swap(int indexA, int indexB) {
        Int temp = elements[indexA];
        Elements[indexA] = elements[indexB];
        Elements[indexB] = temp;
    }
}

This is the largest heap. The first position of the array does not store the element, but starts from the index index 1 and stores the maximum value.

Run test data

public static void main(String[] args) {
    int length = 20;
    Random random = new Random();
    int[] elements = new int[length];
    for (int i = 0; i < length; i++) {
        int ele = random.nextInt(80);
        elements[i] = ele;
        System.out.print(ele + " ");
    }
    BinaryHeap maxHeap = new BinaryHeap(elements);
    System.out.println();
    while (!maxHeap.isEmpty()) {
        System.out.print(maxHeap.pop() + " ");
    }
}

Result output

77 74 56 27 13 23 44 38 35 46 43 51 76 67 78 20 77 12 60 62 
78 77 77 76 74 67 62 60 56 51 46 44 43 38 35 27 23 20 13 12 

One of the largest heap completion.