Detailed explanation of the principles and implementation of Java data structures' minimum heap and maximum heap

This article brings you relevant knowledge about java. In computer science, the implementation of heap is a special data structure based on tree, which can be used on arrays. After constructing the tree structure and satisfying the properties of the heap, let's talk about the heap in the Java data structure. Those who are interested can learn more.

## Recommended study: "

java Video Tutorial"

1. Foreword

History of Heap

The data structure of the heap has many forms, including; 2-3 heap, B heap, Fibonacci heap, and the most commonly used in the Java API is the binary heap used to implement priority queues, which is Introduced by JWJ Williams in 1964 as a data structure for the heapsort algorithm. In addition, the heap is also very important in several efficient graph algorithms such as Dijkstra's algorithm.

2. Heap data structure

In computer science, the implementation of heap is a special data structure based on tree, which can build a tree structure on an array. body, and satisfy the properties of the heap;

Minimum heap: If P is a parent node of C, then the key (or value) of P should be less than or equal to the corresponding value of C.

Maximum heap: Just the opposite of the definition of the minimum heap. In the maximum heap (max heap), the key (or value) of P is greater than the corresponding value of C.

3. Heap code implementation

1. Implementation introduction

The implementation of the heap in the Java API is mainly reflected in the delay queue To implement the binary heap, Brother Fu here separates this part of the code to learn about the implementation of small heaps and large heaps.

From the introduction to the data structure of the heap, we can see that the only difference between a small heap and a large heap is the way of sorting the elements. So that is to say, when storing and retrieving elements, when filling and removing elements, the sorting method is different.

2. Implementation into the heap

When storing elements in the heap, in order to follow its characteristics, the elements at the end of the queue will be compared and migrated upward during the storage process.

private void siftUpComparable(int k, E x) {
    logger.info("【入队】元素：{} 当前队列：{}", JSON.toJSONString(x), JSON.toJSONString(queue));
    while (k > 0) {
        // 获取父节点Idx，相当于除以2
        int parent = (k - 1) >>> 1;
        logger.info("【入队】寻找当前节点的父节点位置。k：{} parent：{}", k, parent);
        Object e = queue[parent];
        // 如果当前位置元素，大于父节点元素，则退出循环
        if (compareTo(x, (E) e) >= 0) {
            logger.info("【入队】值比对，父节点：{} 目标节点：{}", JSON.toJSONString(e), JSON.toJSONString(x));
            break;
        }
        // 相反父节点位置大于当前位置元素，则进行替换
        logger.info("【入队】替换过程，父子节点位置替换，继续循环。父节点值：{} 存放到位置：{}", JSON.toJSONString(e), k);
        queue[k] = e;
        k = parent;
    }
    queue[k] = x;
    logger.info("【入队】完成 Idx：{} Val：{} \r\n当前队列：{} \r\n", k, JSON.toJSONString(x), JSON.toJSONString(queue));
}

The implementation of adding the add method to the heap will eventually call the siftUpComparable method for processing in a sorting manner. This sorting compareTo method is implemented by specific MinHeap and MaxHeap.

Take the heap element 2 as an example, as shown in the figure.

First hang element 2 to the end of the queue, then calculate the position of the parent node through (k - 1) >>> 1, and compare it with the corresponding element. Judgment exchange.

The exchange process includes 2->6, 2->5, and the elements are saved after the exchange is completed.

3. Removing

elements from the heap is actually very simple. Just delete the root element and pop it out directly. But the remaining steps are complicated, because after the root element is migrated, it is necessary to find another minimum element to migrate to the opposite end. This process is exactly the opposite of entering the heap. It is a process of continuous downward migration.

private void siftDownComparable(int k, E x) {
    // 先找出中间件节点
    int half = size >>> 1;
    while (k < half) {
        // 找到左子节点和右子节点，两个节点进行比较，找出最大的值
        int child = (k << 1) + 1;
        Object c = queue[child];
        int right = child + 1;
        // 左子节点与右子节点比较，取最小的节点
        if (right < size && compareTo((E) c, (E) queue[right]) > 0) {
            logger.info("【出队】左右子节点比对，获取最小值。left：{} right：{}", JSON.toJSONString(c), JSON.toJSONString(queue[right]));
            c = queue[child = right];
        }
        // 目标值与c比较，当目标值小于c值，退出循环。说明此时目标值所在位置适合，迁移完成。
        if (compareTo(x, (E) c) <= 0) {
            break;
        }
        // 目标值小于c值，位置替换，继续比较
        logger.info("【出队】替换过程，节点的值比对。上节点：{} 下节点：{} 位置替换", JSON.toJSONString(queue[k]), JSON.toJSONString(c));
        queue[k] = c;
        k = child;
    }
    // 把目标值放到对应位置
    logger.info("【出队】替换结果，最终更换位置。Idx：{} Val：{}", k, JSON.toJSONString(x));
    queue[k] = x;
}

Continuously migrate elements downward. This process will compare the values ​​of the left and right child nodes and find the smallest one. So the whole process will be more troublesome than entering the pile.

Here we take pop-up element 1 as an example, and then replace the element at the end of the heap to the corresponding position. The whole process is divided into 6 pictures.

Figure 1 to Figure 2, find the root element to pop up.
Figure 3 to Figure 4, move the root element downward, compare it with the child elements, and replace the position. If this position is compared with 8 and is less than 8, it will continue to migrate downward.
From Figure 4 to Figure 5, continue the migration. The two sub-elements corresponding to the original node 4 are both larger than 8. You can stop at this time.
Figure 5 to Figure 6, change the element position, replace the element at the end of the queue to the position corresponding to the downward migration detection of element 1.

4. Small heap implementation

The small heap is a positive sequence comparison

public class MinHeap extends Heap<Integer> {

    @Override
    public int compareTo(Integer firstElement, Integer secondElement) {
        return firstElement.compareTo(secondElement);
    }

}

Test

@Test
public void test_min_heap() {
    MinHeap heap = new MinHeap();
    // 存入元素
    heap.add(1);
    heap.add(3);
    heap.add(5);
    heap.add(11);
    heap.add(4);
    heap.add(6);
    heap.add(7);
    heap.add(12);
    heap.add(15);
    heap.add(10);
    heap.add(9);
    heap.add(8);
    // 弹出元素
    while (heap.peek() != null){
        logger.info("测试结果：{}", heap.poll());
    }
}

RESULT

17:21:30.053 [main] INFO queue.PriorityQueue - [Enqueue] Element: 3 Current queue: [1,null,null,null,null,null,null,null,null,null, null]
17:21:30.055 [main] INFO queue.PriorityQueue - [Enter the queue] Find the position of the parent node of the current node. k: 1 parent: 0
17:21:30.056 [main] INFO queue.PriorityQueue - [queue] value comparison, parent node: 1 target node: 3
17:21:30.056 [main] INFO queue.PriorityQueue - [Enter the queue] Complete Idx: 1 Val: 3
Current queue: [1,3,null,null,null,null,null,null,null,null,null]

17:21:30.056 [main] INFO queue.PriorityQueue - [Enqueue] Element: 5 Current queue: [1,3,null,null,null,null,null,null,null,null,null]
17 :21:30.056 [main] INFO queue.PriorityQueue - [Enqueue] Find the position of the parent node of the current node. k: 2 parent: 0
17:21:30.056 [main] INFO queue.PriorityQueue - [queue] value comparison, parent node: 1 target node: 5
17:21:30.056 [main] INFO queue.PriorityQueue - [Enter the queue] Complete Idx: 2 Val: 5
Current queue: [1,3,5,null,null,null,null,null,null,null,null]

17:21:30.056 [main] INFO queue.PriorityQueue - [Enqueue] Element: 11 Current queue: [1,3,5,null,null,null,null,null,null,null,null]
17 :21:30.056 [main] INFO queue.PriorityQueue - [Enqueue] Find the position of the parent node of the current node. k: 3 parent: 1
17:21:30.056 [main] INFO queue.PriorityQueue - [queue] value comparison, parent node: 3 target node: 11
17:21:30.056 [main] INFO queue.PriorityQueue - [Enter the queue] Complete Idx: 3 Val: 11
Current queue: [1,3,5,11,null,null,null,null,null,null,null]

17:21:30.056 [main] INFO queue.PriorityQueue - [Enqueue] Element: 4 Current queue: [1,3,5,11,null,null,null,null,null,null,null]
17 :21:30.056 [main] INFO queue.PriorityQueue - [Enqueue] Find the position of the parent node of the current node. k: 4 parent: 1
17:21:30.056 [main] INFO queue.PriorityQueue - [queue] value comparison, parent node: 3 target node: 4
17:21:30.056 [main] INFO queue.PriorityQueue - [Enter the queue] Complete Idx: 4 Val: 4
Current queue: [1,3,5,11,4,null,null,null,null,null,null]

17:21:30.056 [main] INFO queue.PriorityQueue - [Enqueue] Element: 6 Current queue: [1,3,5,11,4,null,null,null,null,null,null]
17 :21:30.056 [main] INFO queue.PriorityQueue - [Enqueue] Find the position of the parent node of the current node. k: 5 parent: 2
17:21:30.056 [main] INFO queue.PriorityQueue - [queue] value comparison, parent node: 5 target node: 6
17:21:30.056 [main] INFO queue.PriorityQueue - [Enter the queue] Complete Idx: 5 Val: 6
Current queue: [1,3,5,11,4,6,null,null,null,null,null]

17:21:30.056 [main] INFO queue.PriorityQueue - [Enqueue] Element: 7 Current queue: [1,3,5,11,4,6,null,null,null,null,null]
17 :21:30.056 [main] INFO queue.PriorityQueue - [Enqueue] Find the position of the parent node of the current node. k: 6 parent: 2
17:21:30.056 [main] INFO queue.PriorityQueue - [queue] value comparison, parent node: 5 target node: 7
17:21:30.056 [main] INFO queue.PriorityQueue - [Enter the queue] Complete Idx: 6 Val: 7
Current queue: [1,3,5,11,4,6,7,null,null,null,null] 17:21:30.056 [ main] INFO queue.PriorityQueue - [Enqueue] Element: 12 Current queue: [1,3,5,11,4,6,7,null,null,null,null]
17:21:30.056 [main ] INFO queue.PriorityQueue - [Enqueue] Find the position of the parent node of the current node. k: 7 parent: 3
17:21:30.056 [main] INFO queue.PriorityQueue - [queue] value comparison, parent node: 11 target node: 12
17:21:30.056 [main] INFO queue.PriorityQueue - [Enter the queue] Complete Idx: 7 Val: 12
Current queue: [1,3,5,11,4,6,7,12,null,null,null]

17:21:30.056 [main] INFO queue.PriorityQueue - [Enter queue] Element: 15 Current queue: [1,3,5,11,4,6,7,12,null,null,null]
17 :21:30.056 [main] INFO queue.PriorityQueue - [Enqueue] Find the position of the parent node of the current node. k: 8 parent: 3
17:21:30.056 [main] INFO queue.PriorityQueue - [queue] value comparison, parent node: 11 target node: 15
17:21:30.057 [main] INFO queue.PriorityQueue - [Enter the queue] Complete Idx: 8 Val: 15
Current queue: [1,3,5,11,4,6,7,12,15,null,null]

17:21:30.057 [main] INFO queue.PriorityQueue - [Enter queue] Element: 10 Current queue: [1,3,5,11,4,6,7,12,15,null,null]
17 :21:30.057 [main] INFO queue.PriorityQueue - [Enqueue] Find the position of the parent node of the current node. k: 9 parent: 4
17:21:30.057 [main] INFO queue.PriorityQueue - [queue] value comparison, parent node: 4 target node: 10
17:21:30.057 [main] INFO queue.PriorityQueue - [Enter the queue] Complete Idx: 9 Val: 10
Current queue: [1,3,5,11,4,6,7,12,15,10,null]

17:21:30.057 [main] INFO queue.PriorityQueue - [Enter queue] Element: 9 Current queue: [1,3,5,11,4,6,7,12,15,10,null]
17 :21:30.057 [main] INFO queue.PriorityQueue - [Enqueue] Find the position of the parent node of the current node. k：10 parent：4
17:21:30.057 [main] INFO queue.PriorityQueue - [Enter Queue] value comparison, parent node: 4 Target node: 9
17:21:30.057 [main] INFO queue.PriorityQueue - [Enter Queue] completed Idx: 10 Val: 9
Current queue: [1,3,5,11,4,6,7,12,15,10,9]

17:21:30.057 [main] INFO queue.PriorityQueue - [Enqueue] Element: 8 Current queue: [1,3,5,11,4,6,7,12,15,10,9,null,null,null,null,null,null,null ,null,null,null,null,null,null]
17:21:30.057 [main] INFO queue.PriorityQueue - [Enqueue] Find the position of the parent node of the current node. k: 11 parent: 5
17:21:30.057 [main] INFO queue.PriorityQueue - [queue] value comparison, parent node: 6 target node: 8
17:21:30.057 [main] INFO queue.PriorityQueue - [Enter the queue] Complete Idx: 11 Val: 8
Current queue: [1,3,5,11,4,6,7,12,15,10,9,8,null,null, null,null,null,null,null,null,null,null,null,null]

17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] Replacement process, node value ratio right. Upper node: 1 Lower node: 3 Position replacement
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] Compare the left and right child nodes to obtain the minimum value. left: 11 right: 4
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] replacement process, node value comparison. Upper node: 3 Lower node: 4 Position replacement
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] Compare the left and right child nodes to obtain the minimum value. left: 10 right: 9
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] Replace the result and finally change the position. Idx: 4 Val: 8
17:21:30.057 [main] INFO heap.__test__.HeapTest - Test result: 1
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] Replacement process , node value comparison. Upper node: 3 Lower node: 4 Position replacement
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] Compare the left and right child nodes to obtain the minimum value. left: 11 right: 8
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] replacement process, node value comparison. Upper node: 4 Lower node: 8 Position replacement
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] Replacement result, final replacement position. Idx: 4 Val: 9
17:21:30.057 [main] INFO heap.__test__.HeapTest - Test result: 3
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] Left and right children Compare nodes to obtain the minimum value. left: 8 right: 5
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] replacement process, node value comparison. Upper node: 4 Lower node: 5 Position replacement
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] replacement process, node value comparison. Upper node: 5 Lower node: 6 Position replacement
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] Replacement result, final replacement position. Idx: 5 Val: 10
17:21:30.057 [main] INFO heap.__test__.HeapTest - Test result: 4
17:21:30.057 [main] INFO queue.PriorityQueue - [Dequeue] Left and right children Compare nodes to obtain the minimum value. left: 8 right: 6
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] replacement process, node value comparison. Upper node: 5 Lower node: 6 Position replacement
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] Compare the left and right child nodes to obtain the minimum value. left: 10 right: 7
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] replacement process, node value comparison. Upper node: 6 Lower node: 7 Position replacement
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] Replacement result, final replacement position. Idx: 6 Val: 15
17:21:30.058 [main] INFO heap.__test__.HeapTest - Test result: 5
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] Left and right children Compare nodes to obtain the minimum value. left: 8 right: 7
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] replacement process, node value comparison. Upper node: 6 Lower node: 7 Position replacement
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] replacement process, node value comparison. Upper node: 7 Lower node: 10 Position replacement
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] Replace the result and finally change the position. Idx: 5 Val: 12
17:21:30.058 [main] INFO heap.__test__.HeapTest - Test result: 6
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] Replacement process , node value comparison. Upper node: 7 Lower node: 8 Position replacement
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] Compare the left and right child nodes to obtain the minimum value. left: 11 right: 9
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] replacement process, node value comparison. Upper node: 8 Lower node: 9 Position replacement
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] Replacement result, final replacement position. Idx: 4 Val: 15
17:21:30.058 [main] INFO heap.__test__.HeapTest - Test result: 7
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] Replacement process , node value comparison. Upper node: 8 Lower node: 9 Position replacement
17:21:30.058 [main] INFO queue.PriorityQueue - [Dequeue] replacement process, node value comparison. Upper node: 9 Lower node: 11 Position replacement
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换结果，最终更换位置。Idx：3 Val：12
17:21:30.058 [main] INFO heap.__test__.HeapTest - 测试结果：8
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】左右子节点比对，获取最小值。left：11 right：10
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换过程，节点的值比对。上节点：9 下节点：10 位置替换
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换结果，最终更换位置。Idx：2 Val：15
17:21:30.058 [main] INFO heap.__test__.HeapTest - 测试结果：9
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换过程，节点的值比对。上节点：10 下节点：11 位置替换
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换结果，最终更换位置。Idx：1 Val：12
17:21:30.058 [main] INFO heap.__test__.HeapTest - 测试结果：10
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换过程，节点的值比对。上节点：11 下节点：12 位置替换
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换结果，最终更换位置。Idx：1 Val：15
17:21:30.058 [main] INFO heap.__test__.HeapTest - 测试结果：11
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换结果，最终更换位置。Idx：0 Val：15
17:21:30.058 [main] INFO heap.__test__.HeapTest - 测试结果：12
17:21:30.058 [main] INFO heap.__test__.HeapTest - 测试结果：15

Process finished with exit code 0
小堆就是一个正序的输出结果，从小到大的排序和输出。
小堆空间：[1,3,5,11,4,6,7,12,15,10,9,8,null,null,null,null,null,null,null,null,null,null,null,null]

• 小堆就是一个正序的输出结果，从小到大的排序和输出。
• 小堆空间：[1,3,5,11,4,6,7,12,15,10,9,8,null,null,null,null,null,null,null,null,null,null,null,null]

5. 大堆实现

小堆是一个反序比对

public class MaxHeap extends Heap<Integer> {

    @Override
    public int compareTo(Integer firstElement, Integer secondElement) {
        return secondElement.compareTo(firstElement);
    }

}

测试

@Test
public void test_max_heap() {
    MaxHeap heap = new MaxHeap();
    // 存入元素
    heap.add(1);
    heap.add(3);
    heap.add(5);
    heap.add(11);
    heap.add(4);
    heap.add(6);
    heap.add(7);
    heap.add(12);
    heap.add(15);
    heap.add(10);
    heap.add(9);
    heap.add(8);
    // 弹出元素
    while (heap.peek() != null){
        logger.info("测试结果：{}", heap.poll());
    }
}

结果

17:23:45.079 [main] INFO queue.PriorityQueue - [Enqueue] Element: 3 Current queue: [1,null,null,null,null,null,null,null,null,null, null]
17:23:45.081 [main] INFO queue.PriorityQueue - [Enter the queue] Find the position of the parent node of the current node. k: 1 parent: 0
17:23:45.081 [main] INFO queue.PriorityQueue - [Enqueue] replacement process, replace the parent and child node positions, and continue the cycle. Parent node value: 1 Stored in location: 1
17:23:45.081 [main] INFO queue.PriorityQueue - [Enter queue] Complete Idx: 0 Val: 3
Current queue: [3,1,null, null,null,null,null,null,null,null,null]

17:23:45.081 [main] INFO queue.PriorityQueue - [Enqueue] Element: 5 Current queue: [3,1, null,null,null,null,null,null,null,null,null]
17:23:45.081 [main] INFO queue.PriorityQueue - [Enqueue] Find the position of the parent node of the current node. k: 2 parent: 0
17:23:45.081 [main] INFO queue.PriorityQueue - [Enqueue] replacement process, replace the parent and child node positions, and continue the cycle. Parent node value: 3 Stored in location: 2
17:23:45.081 [main] INFO queue.PriorityQueue - [Enter queue] Complete Idx: 0 Val: 5
Current queue: [5,1,3, null,null,null,null,null,null,null,null]

17:23:45.081 [main] INFO queue.PriorityQueue - [Enqueue] Element: 11 Current queue: [5,1, 3,null,null,null,null,null,null,null,null]
17:23:45.081 [main] INFO queue.PriorityQueue - [Enter the queue] Find the position of the parent node of the current node. k: 3 parent: 1
17:23:45.081 [main] INFO queue.PriorityQueue - [Enqueue] replacement process, replace the parent and child node positions, and continue the cycle. Parent node value: 1 Stored in location: 3
17:23:45.081 [main] INFO queue.PriorityQueue - [Enter the queue] Find the parent node position of the current node. k: 1 parent: 0
17:23:45.081 [main] INFO queue.PriorityQueue - [Enqueue] replacement process, replace the parent and child node positions, and continue the cycle. Parent node value: 5 Stored in location: 1
17:23:45.081 [main] INFO queue.PriorityQueue - [Enter queue] Complete Idx: 0 Val: 11
Current queue: [11,5,3, 1,null,null,null,null,null,null,null]

17:23:45.081 [main] INFO queue.PriorityQueue - [Enqueue] Element: 4 Current queue: [11,5, 3,1,null,null,null,null,null,null,null]
17:23:45.082 [main] INFO queue.PriorityQueue - [Enqueue] Find the position of the parent node of the current node. k: 4 parent: 1
17:23:45.082 [main] INFO queue.PriorityQueue - [queue] value comparison, parent node: 5 target node: 4
17:23:45.082 [main] INFO queue.PriorityQueue - [Enter the queue] Complete Idx: 4 Val: 4
Current queue: [11,5,3,1,4,null,null,null,null,null,null]

17:23:45.082 [main] INFO queue.PriorityQueue - [Enqueue] Element: 6 Current queue: [11,5,3,1,4,null,null,null,null,null,null]
17 :23:45.082 [main] INFO queue.PriorityQueue - [Enqueue] Find the position of the parent node of the current node. k: 5 parent: 2
17:23:45.082 [main] INFO queue.PriorityQueue - [Enqueue] replacement process, replace the parent and child node positions, and continue the cycle. Parent node value: 3 Stored in location: 5
17:23:45.082 [main] INFO queue.PriorityQueue - [Enter the queue] Find the parent node position of the current node. k: 2 parent: 0
17:23:45.082 [main] INFO queue.PriorityQueue - [queue] value comparison, parent node: 11 target node: 6
17:23:45.082 [main] INFO queue.PriorityQueue - [Enter the queue] Complete Idx: 2 Val: 6
Current queue: [11,5,6,1,4,3,null,null,null,null,null]

17:23:45.082 [main] INFO queue.PriorityQueue - [Enqueue] Element: 7 Current queue: [11,5,6,1,4,3,null,null,null,null,null]
17 :23:45.082 [main] INFO queue.PriorityQueue - [Enqueue] Find the position of the parent node of the current node. k: 6 parent: 2
17:23:45.082 [main] INFO queue.PriorityQueue - [Enqueue] replacement process, replace the parent and child node positions, and continue the cycle. Parent node value: 6 Stored in location: 6
17:23:45.082 [main] INFO queue.PriorityQueue - [Enter the queue] Find the parent node position of the current node. k: 2 parent: 0
17:23:45.082 [main] INFO queue.PriorityQueue - [queue] value comparison, parent node: 11 target node: 7
17:23:45.082 [main] INFO queue.PriorityQueue - [Enter the queue] Complete Idx: 2 Val: 7
Current queue: [11,5,7,1,4,3,6,null,null,null,null]

17:23:45.082 [main] INFO queue.PriorityQueue - [Enqueue] Element: 12 Current queue: [11,5,7,1,4,3,6,null,null,null,null]
17 :23:45.082 [main] INFO queue.PriorityQueue - [Enqueue] Find the position of the parent node of the current node. k: 7 parent: 3
17:23:45.082 [main] INFO queue.PriorityQueue - [Enqueue] replacement process, replace the parent and child node positions, and continue the cycle. Parent node value: 1 Stored in location: 7
17:23:45.082 [main] INFO queue.PriorityQueue - [Enter the queue] Find the parent node position of the current node. k: 3 parent: 1
17:23:45.082 [main] INFO queue.PriorityQueue - [Enqueue] replacement process, replace the parent and child node positions, and continue the cycle. Parent node value: 5 Stored in location: 3
17:23:45.082 [main] INFO queue.PriorityQueue - [Enter the queue] Find the parent node position of the current node. k：1 parent：0
17:23:45.082 [main] INFO queue.PriorityQueue - [Enqueue] Replacement process, the position of the parent and child nodes is replaced, and the cycle continues. Parent node value: 11 Stored in location: 1
17:23:45.082 [main] INFO queue.PriorityQueue - [Enter queue] Complete Idx: 0 Val: 12
Current queue: [12,11,7, 5,4,3,6,1,null,null,null]

17:23:45.082 [main] INFO queue.PriorityQueue - [Enqueue] Element: 15 Current queue: [12,11, 7,5,4,3,6,1,null,null,null]
17:23:45.082 [main] INFO queue.PriorityQueue - [Enter the queue] Find the position of the parent node of the current node. k: 8 parent: 3
17:23:45.082 [main] INFO queue.PriorityQueue - [Enter the queue] Replacement process, the position of the parent and child nodes is replaced, and the cycle continues. Parent node value: 5 Stored in location: 8
17:23:45.082 [main] INFO queue.PriorityQueue - [Enter the queue] Find the parent node position of the current node. k: 3 parent: 1
17:23:45.082 [main] INFO queue.PriorityQueue - [Enqueue] replacement process, replace the parent and child node positions, and continue the cycle. Parent node value: 11 Stored in location: 3
17:23:45.082 [main] INFO queue.PriorityQueue - [Enter the queue] Find the parent node position of the current node. k: 1 parent: 0
17:23:45.082 [main] INFO queue.PriorityQueue - [Enqueue] replacement process, replace the parent and child node positions, and continue the cycle. Parent node value: 12 Stored in location: 1
17:23:45.082 [main] INFO queue.PriorityQueue - [Enter queue] Complete Idx: 0 Val: 15
Current queue: [15,12,7, 11,4,3,6,1,5,null,null]

17:23:45.082 [main] INFO queue.PriorityQueue - [Enqueue] Element: 10 Current queue: [15,12, 7,11,4,3,6,1,5,null,null]
17:23:45.082 [main] INFO queue.PriorityQueue - [Enter the queue] Find the position of the parent node of the current node. k: 9 parent: 4
17:23:45.083 [main] INFO queue.PriorityQueue - [Enqueue] replacement process, replace the parent and child node positions, and continue the cycle. Parent node value: 4 Stored in location: 9
17:23:45.083 [main] INFO queue.PriorityQueue - [Enter the queue] Find the parent node position of the current node. k: 4 parent: 1
17:23:45.083 [main] INFO queue.PriorityQueue - [queue] value comparison, parent node: 12 target node: 10
17:23:45.083 [main] INFO queue.PriorityQueue - [Enter the queue] Complete Idx: 4 Val: 10
Current queue: [15,12,7,11,10,3,6,1,5,4,null]

17:23:45.083 [main] INFO queue.PriorityQueue - [Enter queue] Element: 9 Current queue: [15,12,7,11,10,3,6,1,5,4,null]
17 :23:45.083 [main] INFO queue.PriorityQueue - [Enqueue] Find the position of the parent node of the current node. k: 10 parent: 4
17:23:45.083 [main] INFO queue.PriorityQueue - [queue] value comparison, parent node: 10 target node: 9
17:23:45.083 [main] INFO queue.PriorityQueue - [Enter the queue] Complete Idx: 10 Val: 9
Current queue: [15,12,7,11,10,3,6,1,5,4,9]

17:23:45.083 [main] INFO queue.PriorityQueue - [Enqueue] Element: 8 Current queue: [15,12,7,11,10,3,6,1,5,4,9,null,null, null,null,null,null,null,null,null,null,null,null,null]
17:23:45.083 [main] INFO queue.PriorityQueue - [Enter the queue] Find the position of the parent node of the current node. k: 11 parent: 5
17:23:45.083 [main] INFO queue.PriorityQueue - [Enter the queue] Replacement process, the position of the parent and child nodes is replaced, and the cycle continues. Parent node value: 3 Stored in location: 11
17:23:45.083 [main] INFO queue.PriorityQueue - [Enter the queue] Find the parent node position of the current node. k: 5 parent: 2
17:23:45.083 [main] INFO queue.PriorityQueue - [Enqueue] replacement process, replace the parent and child node positions, and continue the cycle. Parent node value: 7 Stored in location: 5
17:23:45.083 [main] INFO queue.PriorityQueue - [Enter the queue] Find the parent node position of the current node. k: 2 parent: 0
17:23:45.083 [main] INFO queue.PriorityQueue - [queue] value comparison, parent node: 15 target node: 8
17:23:45.083 [main] INFO queue.PriorityQueue - [Enter the queue] Complete Idx: 2 Val: 8
Current queue: [15,12,8,11,10,7,6,1,5,4,9,3,null,null, null,null,null,null,null,null,null,null,null,null]

17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] Replacement process, node value ratio right. Upper node: 15 Lower node: 12 Position replacement
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] Replacement process, node value comparison. Upper node: 12 Lower node: 11 Position replacement
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] Compare the left and right child nodes to obtain the minimum value. left: 1 right: 5
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] replacement process, node value comparison. Upper node: 11 Lower node: 5 Position replacement
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] Replace the result and finally change the position. Idx: 8 Val: 3
17:23:45.083 [main] INFO heap.__test__.HeapTest - Test result: 15
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] Replacement process , node value comparison. Upper node: 12 Lower node: 11 Position replacement
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] Compare the left and right child nodes to obtain the minimum value. left：5 right：10
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] Replacement process, node value comparison. Upper node: 11 Lower node: 10 Position replacement
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] Replace the result and finally change the position. Idx: 4 Val: 9
17:23:45.083 [main] INFO heap.__test__.HeapTest - Test result: 12
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] Replacement process , node value comparison. Upper node: 11 Lower node: 10 Position replacement
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] Compare the left and right child nodes to obtain the minimum value. left: 5 right: 9
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] replacement process, node value comparison. Upper node: 10 Lower node: 9 Position replacement
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] Replace the result and finally change the position. Idx: 4 Val: 4
17:23:45.083 [main] INFO heap.__test__.HeapTest - Test result: 11
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] Replacement process , node value comparison. Upper node: 10 Lower node: 9 Position replacement
17:23:45.083 [main] INFO queue.PriorityQueue - [Dequeue] replacement process, node value comparison. Upper node: 9 Lower node: 5 Position replacement
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] Replacement result, final replacement position. Idx: 3 Val: 3
17:23:45.084 [main] INFO heap.__test__.HeapTest - Test result: 10
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] Left and right children Compare nodes to obtain the minimum value. left: 5 right: 8
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] replacement process, node value comparison. Upper node: 9 Lower node: 8 Position replacement
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] replacement process, node value comparison. Upper node: 8 Lower node: 7 Position replacement
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] Replacement result, final replacement position. Idx: 5 Val: 1
17:23:45.084 [main] INFO heap.__test__.HeapTest - Test result: 9
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] Left and right children Compare nodes to obtain the minimum value. left: 5 right: 7
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] replacement process, node value comparison. Upper node: 8 Lower node: 7 Position replacement
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] Replacement result, final replacement position. Idx: 2 Val: 6
17:23:45.084 [main] INFO heap.__test__.HeapTest - Test result: 8
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] Left and right children Compare nodes to obtain the minimum value. left: 5 right: 6
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] replacement process, node value comparison. Upper node: 7 Lower node: 6 Position replacement
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] Replacement result, final replacement position. Idx: 2 Val: 1
17:23:45.084 [main] INFO heap.__test__.HeapTest - Test result: 7
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] Replacement process , node value comparison. Upper node: 6 Lower node: 5 Position replacement
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] Replacement result, final replacement position. Idx: 1 Val: 4
17:23:45.084 [main] INFO heap.__test__.HeapTest - Test result: 6
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] Replacement process , node value comparison. Upper node: 5 Lower node: 4 Position replacement
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] Replacement result, final replacement position. Idx: 1 Val: 3
17:23:45.084 [main] INFO heap.__test__.HeapTest - Test result: 5
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] Replacement process , node value comparison. Upper node: 4 Lower node: 3 Position replacement
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] Replacement result, final replacement position. Idx: 1 Val: 1
17:23:45.084 [main] INFO heap.__test__.HeapTest - Test result: 4
17:23:45.084 [main] INFO queue.PriorityQueue - [Dequeue] Replacement result , eventually changing positions. Idx: 0 Val: 1
17:23:45.084 [main] INFO heap.__test__.HeapTest - Test result: 3
17:23:45.084 [main] INFO heap.__test__.HeapTest - Test result: 1

Process finished with exit code 0

The big pile is a reverse output result, sorted and output from large to small.

Big pile of space: [15,12,8,11,10,7,6,1,5,4,9,3,null,null,null,null,null,null,null,null ,null,null,null,null]

Recommended learning: "java video tutorial"

The above is the detailed content of Detailed explanation of the principles and implementation of Java data structures' minimum heap and maximum heap. For more information, please follow other related articles on the PHP Chinese website!