Stacks of data structures and algorithms

preface

I haven’t updated it for a long time recently. On the one hand, I am a little busy, and the business code needs to move. On the other hand, there are always some small things in life that interrupt the rhythm. All in all, yeah, I’m just lazy. I admit, I don’t deserve it, boo-hoo.

So I’ve updated it… The data structure that I’m going to talk about in this lecture is often paired with the stack, so he’s the stack’s brother.

define

As usual, let’s start with the definition of a heap. Here’s how Wikipedia defines a heap

In computer science, a heap is a specialized tree-based data structure which is essentially an almost complete tree that satisfies the heap property: in a max heap, for any given node C, if P is a parent node of C, then the key (the value) of P is greater than or equal to the key of C. In a min heap, the key of P is less than or equal to the key of C. The node at the “top” of the heap (with no parents) is called the root node.

Basically, you take a complete binary tree and you add some special properties.

The nature of the

  1. Complete binary tree

    The heap must first be a complete binary tree, at which point you must ask Koizumi what a complete binary tree is.

    Wait for Mr Koizumi to draw a picture to everyone xue micro explain.

In the figure, nodes are numbered from top to bottom starting from the root node and then from left to right in each layer. If the serial number of each node is consistent with that in the state of full binary tree (each layer has reached the maximum number of nodes), it is considered as a complete binary tree. Generally speaking, for a complete binary tree, only when the nodes in each layer are not empty can there be children, and there must be left children and then right children. If you look at the picture, you can see that a full binary tree is also a complete binary tree.

  1. The node value is larger/smaller than the child node

    Maximum heap: Each node is larger than its left and right children

    Minimum heap: Each node is smaller than its left and right children

The construction of the heap

Theoretically, heap construction can be understood as node insertion or node sinking:

Insert the new node into the child node of the old node to float up.

Sinking is when a new node is “inserted” from the top of the heap each time, which in turn requires sinking from the top of the heap each time.

In fact, if we are given an array, we can treat the array as a complete binary tree:

Sink from the parent of the leaf to the “top of the heap”.

If you’ve ever looked at the source code for the Java PriorityQueue (small top heap by default), you’ll see that it actually contains an array with an initial size of 11.Before performing a series of operations on the heap, let’s warm it up. There are two very important bottom operations in using the heap: sink and float.

sinking

Sinking is also called heapification. When it is found that the node element is larger than the child node (minimum heap) or smaller than the child node (maximum heap), the value of the node is exchanged with the value of the larger child node (minimum heap) or smaller node (maximum heap), which is the sinking operation. Purpose :(1) delete the top of the heap after the heap (2) create a heap

void siftDown(int index) {
        if (index == size) return;
        int childIndex = 2 * index + 1;
        int tmp = heap[index];
        while(childIndex <= size) {
            if (childIndex + 1 <= size && heap[childIndex] < heap[childIndex + 1]) {
                childIndex++;
            }
            if (heap[childIndex]<= tmp) break;
            heap[index] = heap[childIndex];
            index = childIndex;
            childIndex = 2 * index + 1;
        }
        heap[index] = tmp;
    }
Copy the code

floating

When a node element is found to be smaller than the parent node (minimum heap) or larger than the parent node (maximum heap), the value of the node is swapped with the value of the parent node, which is called floating up. Purpose: Heap insertion

void siftUp(int index) {
        if (index ==1) return;
        int parentIndex = index/2;
        int tmp = heap[index];
        while (parentIndex >=1 && heap[parentIndex] < heap[index]) {
            heap[index] = heap[parentIndex];
            index = parentIndex;
            parentIndex = index / 2;
        }
        heap[index] = tmp;
    }
Copy the code

insert

For the operation of the insert. Keep in mind that the new node is inserted as a leaf node in the form of a full binary tree. Then float the node up. Here’s an example: insert 13 into [12, 10,9, 5, 6, 8] that already fits the heap structure

  1. First, insert 13 into the right child node of 9 according to the child node, which conforms to the properties of a complete binary tree.
  2. So if I float up 13, compared to 9, the second property of the largest heap, the node is bigger than the child node, so I switch with 9, and I float up.
  3. Repeat the operation of 2 until it fails to float (there are two possibilities of failing to float, one is to reach the top of the heap, the other is not to meet the conditions of floating)

The process diagram is dissected as follows

delete

For the operation of the delete. Keep in mind that when the last element is found, the value of the node to be deleted is interchanged with the value of the last node, and the last node is removed. Then sink the node after the interchange. Example: delete 12 from [12, 10,9, 5, 6, 8] that already conforms to the heap structure

  1. Swap 12 with 8, then delete the last node
  2. The second property of the largest heap is that the node is larger than the child node, so it is switched with the larger child node 10 and continues to sink.
  3. Repeat step 2 until subsidence is no longer possible

The process diagram is dissected as follows

Complexity analysis

operation Time complexity Time complexity
The heap to create O(N) O(N)
Heap of insert O(logN) O(logN)
Delete the heaptop element O(logN) O(logN)
In fact, the main operations of heap are these three, insert heap, delete heap top element \
The heap is a relatively less complex data structure, but it’s good for certain kinds of problems-sorting problems, the first K elements, the KTH element, and so on.

application

Heap sort

Due to the nature of the heap, the heap top of the largest heap must be the maximum, the heap top of the smallest heap must be the minimum, so the new heap top after removing the top is the next largest (or smaller) value, and so on.

public class HeapSort {
    / / heap sort
    public static int[] heapSort(int[] nums) {
        int n = nums.length;
        int i,tmp;
        // Build the big top heap
        for(i=(n-2) /2; i>=0; i--) {// Start from the parent with only one layer of children and descend to the root of the tree
            shiftDown(nums,i,n-1);
        }
        // Sort the heap, remove the top of the heap, and the top is still the largest after the heap reconstruction
        for(i=n-1; i>=1; i--){// The process of removing the top of the heap is to replace the top of the heap with the value of the last node, and then delete the last node
            tmp = nums[i];
            nums[i] = nums[0];
            nums[0] = tmp;
            shiftDown(nums,0,i-1);
        }
        return nums;
    }

    // Small element drop operation
    public static void shiftDown(int[] nums, int parentIndex, int n) {
        // Temporarily save the element to sink
        int temp = nums[parentIndex];
        // The position of the left child node
        int childIndex = 2 * parentIndex + 1;
        while (childIndex <= n) {
            // If the right child is larger than the left, swap with the right child
            if(childIndex + 1 <= n && nums[childIndex] < nums[childIndex + 1])
                childIndex++;
            if (nums[childIndex] <= temp ) break;// This child node conforms to the characteristics of the big top heap
            // Note that since we are heapsort from a node of height 1, there is no need to worry that the children of nodal nodes do not conform to the heap characteristics
            // The parent node sinks
            nums[parentIndex] = nums[childIndex];
            parentIndex = childIndex;
            childIndex = 2 * parentIndex + 1;
        }
        nums[parentIndex] = temp;
    }

    public static void main(String[] args) {
        int[] a = {91.60.96.13.35.65.81.46.13.10.30.20.31.77.81.22};
        System.out.print("Pre-sort array A: \n");
        for(int i:a) {
            System.out.print(i);
            System.out.print("");
        }
        a=heapSort(a);
        System.out.print(\n Sorted array A: \n);
        for(int i:a) {
            System.out.print(i);
            System.out.print(""); }}}Copy the code

Top K problem

Top K problem is a general name of a class of problems, mainly to select K elements that meet the maximum conditions before meeting a certain condition.

The title

Given a non-empty array of integers, return the element with the highest occurrence frequency of K. \

Example 1: input: nums =,1,1,2,2,3 [1], k = 2 output: [1, 2] example 2: input: nums = [1], k = 1 output: [1]

parsing

All elements are added to the small top heap, and if there are more than K elements, the top is removed for each additional element that is more satisfying than the top of the heap, and the element is inserted.

code

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        The first element of int[] represents the value of the array, and the second element represents the number of occurrences of that value
        PriorityQueue<int[]> queue = new PriorityQueue<int[] > (new Comparator<int[] > () {public int compare(int[] pre, int[] nex) {
                return pre[1] - nex[1]; }});for (int key : map.keySet()) {
            int value = map.get(key);
            if (queue.size() == k) {
                if (queue.peek()[1] < value) {
                    queue.poll();
                    queue.add(new int[]{key, value}); }}else {
                queue.add(new int[]{key, value}); }}int[] kMax = new int[k];
        for (int i = 0; i < k; ++i) {
                kMax[i] = queue.poll()[0];
        }
        returnkMax; }}Copy the code

conclusion

The heap data structure is much simpler than red-black tree, B+ tree and other structures. It is not difficult to build a heap by mastering the two properties of the heap, sinking and floating operations. Of course, after understanding the construction process of the heap, it is more about how to use this data structure. The PriorityQueue (PriorityQueue) class is a set of classes that can be used as a heap. At present in the construction of their own website, interested also can pay attention to: Koizumi’s development of the road of cultivation