How to create a heap of Java data structures

Properties of the heap

The heap is logically a complete binary tree, and the heap is physically stored in an array.

Summary: A complete binary tree is stored in an array using level-order traversal. The main usage of this method is heap representation.

And if the subscript of the father (parent) is known,

then: left child (left) subscript = 2 * parent 1;

right child (right) Subscript = 2 * parent 2;

Known child (no distinction between left and right) (child) subscript, then:

Parent (parent) subscript = (child - 1) / 2 ;

Classification of heaps

Big heap: A complete binary tree in which the root node is greater than the left and right child nodes (the parent node is greater than its child nodes) is called a big heap, or a big root heap, or a maximum heap.

Small heap: A complete binary tree in which the root node is smaller than the two left and right child nodes is called a small heap (the parent node is smaller than its child nodes), or a small root heap, or a minimum heap.

Downward adjustment of the heap

Now there is an array, which is logically a complete binary tree. We can use the downward adjustment algorithm starting from the root node to It adjusts to a small pile or a large pile. The downward adjustment algorithm has a premise: the left and right subtrees must be a heap before they can be adjusted.

Take a small heap as an example:

1. First, let the left and right child nodes compare and take the minimum value.

2. Compare the smaller child node with the parent node. If the child node

3. The cycle repeats. If the subscript of the child node is out of bounds, it means that it has reached the end and it is over.

Code example:

 //parent: 每棵树的根节点
 //len: 每棵树的调整的结束位置
public void shiftDown(int parent,int len){
        int child=parent*2+1; //因为堆是完全二叉树，没有左孩子就一定没有右孩子，所以最起码是有左孩子的，至少有1个孩子
        while(child<len){
            if(child+1<len && elem[child]<elem[child+1]){
                child++;//两孩子结点比较取较小值
            }
            if(elem[child]<elem[parent]){
                int tmp=elem[parent];
                elem[parent]=elem[child];
                elem[child]=tmp;
                parent=child;
                child=parent*2+1;
            }else{
                break;
            }
        }
    }

Creation of heap

Given an array, this array can be logically regarded as a complete binary tree , but it is not yet a heap (the left and right subtrees are not both large or small). Now we use the algorithm to build it into a heap (large or small). how should I do it? Here we start adjusting from the first subtree of the last non-leaf node, and adjust it all the way to the tree of the root node, and then we can adjust it into a pile. Here we will use the downward adjustment we just wrote.

public void creatHeap(int[] arr){
        for(int i=0;i<arr.length;i++){
            elem[i]=arr[i];
            useSize++;
        }
        for(int parent=(useSize-1-1)/2;parent>=0;parent--){//数组下标从0开始
            shiftDown(parent,useSize);
        }
    }

The space complexity of building a heap is O(N), because the heap is a complete binary tree, and a full binary tree is also a complete binary tree. We use a full binary tree (in the worst case) to prove it.

The heap must be adjusted upward

Now there is a heap, we need to insert data at the end of the heap, and then adjust it so that it still maintains the heap structure, this is an upward adjustment.

Take a large heap as an example:

Code example:

public void shiftup(int child){
        int parent=(child-1)/2;
        while(child>0){
            if(elem[child]>elem[parent]){
                int tmp=elem[parent];
                elem[parent]=elem[child];
                elem[child]=tmp;
                child=parent;
                parent=(child-1)/2;
            }else{
                break;
            }
        }
    }

Common operations on the heap

Enter queue

To add an element to the heap, add it to the last position, and then adjust it upward.

public boolean isFull(){
        return elem.length==useSize;
    }
public void offer(int val){
        if(isFull()){
            elem= Arrays.copyOf(elem,2*elem.length);//扩容
        }
        elem[useSize++]=val;
        shiftup(useSize-1);
    }

Dequeue

To delete elements from the heap, swap the top element of the heap with the last element, then decrease the size of the entire array by one, and finally adjust it downward to delete the top of the stack. element.

public boolean isEmpty(){
        return useSize==0;
    }
public int poll(){
        if(isEmpty()){
            throw new RuntimeException("优先级队列为空");
        }
        int tmp=elem[0];
        elem[0]=elem[useSize-1];
        elem[useSize-1]=tmp;
        useSize--;
        shiftDown(0,useSize);
        return tmp;
    }

Get the first element of the team

public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("优先级队列为空");
        }
        return elem[0];
    }

TopK Question

Give you 6 data, find the top 3 largest data. How do we use the heap at this time?

Problem-solving ideas:

1. If you want to find the top K largest elements, you need to build a small root heap.

2. If you want to find the first K smallest elements, you need to build a large root heap.

3. The Kth largest element. Build a small heap, and the top element of the heap is the Kth largest element.

4. The Kth smallest element. Build a big heap, and the top element of the heap is the Kth largest element.

Example

For example: Find the first n largest data

##Code example:

 public static int[] topK(int[] array,int k){
        //创建一个大小为K的小根堆
        PriorityQueue<Integer> minHeap=new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1-o2;
            }
        });
        //遍历数组中元素，将前k个元素放入队列中
        for(int i=0;i<array.length;i++){
            if(minHeap.size()<k){
                minHeap.offer(array[i]);
            }else{
                //从k+1个元素开始，分别和堆顶元素比较
                int top=minHeap.peek();
                if(array[i]>top){
                    //先弹出后存入
                    minHeap.poll();
                    minHeap.offer(array[i]);
                }
            }
        }
        //将堆中元素放入数组中
        int[] tmp=new int[k];
        for(int i=0;i< tmp.length;i++){
            int top=minHeap.poll();
            tmp[i]=top;
        }
        return tmp;
    }
    public static void main(String[] args) {
        int[] array={12,8,23,6,35,22};
        int[] tmp=topK(array,3);
        System.out.println(Arrays.toString(tmp));
    }

Result:

Array sorting

Furthermore, if you want to sort an array from small to large, should you use a large root heap or a small root heap?

---->Big root heap

Code example:

  public void heapSort(){
        int end=useSize-1;
        while(end>0){
            int tmp=elem[0];
            elem[0]=elem[end];
            elem[end]=tmp;
            shiftDown(0,end);//假设这里向下调整为大根堆
            end--;
        }
    }

The above is the detailed content of How to create a heap of Java data structures. For more information, please follow other related articles on the PHP Chinese website!