Shulou(Shulou.com)06/01 Report--

This article will explain in detail how Java implements binary heap, big top heap and small top heap. The editor thinks it is very practical, so I share it with you as a reference. I hope you can get something after reading this article.

What is a binary pile?

A binary heap is a complete binary tree, or a binary tree close to a complete binary tree structure. When building a binary tree, taking the preorder to build a tree is a complete binary tree. That's the binary heap. Therefore, the process of building a binary reactor is theoretically the same as that of pre-order building.

What is the big top pile and the small top pile?

Binary heap is essentially a nearly complete binary tree, so large top pile and small top pile must also meet the requirements of this structure. On top of this, the large top heap requires that for a node, its left and right nodes are smaller than it; for a small top heap, its left and right nodes are larger than it.

Build a pile

Binary heap building is essentially similar to pre-order heap building, except that one thing to consider is the size relationship, which is somewhat similar to binary search tree building, so it can be concluded that building trees is essentially recursive trees, but because the size requirements of the data structure are different, the judgment functions required are not the same, and where the nodes enter is not the same.

Large-top and small-top reactors are also divided into stable and unstable ones. Stability and instability means that if they have the same value, then their insertion order should be the same as the order of the nodes.

Program realization

First, define the basic heap structure

Public class BinaryHeap {private Integer value; private BinaryHeap leftChild; private BinaryHeap rightChild;}

The process of building pile is consistent with that of building binary tree.

Public static BinaryHeap buildHeap (BinaryHeap binaryHeap, Integer value) {if (Objects.isNull (binaryHeap)) binaryHeap = new BinaryHeap (); if (Objects.isNull (binaryHeap.getValue () {binaryHeap.setValue (value); return binaryHeap;} if (Objects.isNull (binaryHeap.getLeftChild () {BinaryHeap binaryHeap1 = new BinaryHeap (); binaryHeap1.setValue (value); binaryHeap.setLeftChild (binaryHeap1) } else if (Objects.nonNull (binaryHeap.getLeftChild () {if (Objects.isNull (binaryHeap.getRightChild () {BinaryHeap binaryHeap1 = new BinaryHeap (); binaryHeap1.setValue (value); binaryHeap.setRightChild (binaryHeap1) } else {/ / TODO: neither node is null if (checkNull (binaryHeap.getLeftChild () buildHeap (binaryHeap.getLeftChild (), value); else if (checkNull (binaryHeap.getRightChild () buildHeap (binaryHeap.getRightChild (), value); else buildHeap (binaryHeap.getLeftChild (), value);}} return binaryHeap;}

The main principle is that if the left node of the current node is empty, the current value is placed on the left node, and if the left node is not empty and the right node is empty, the value is placed on the right node. If the left and right nodes are not empty, transfer the tree building process to the next layer, if the left node has empty child nodes, transfer to the left node, if the left node has no empty child nodes, and the right node has empty child nodes, then transfer to the right node. If neither left or right node has an empty child node, it is also transferred to the left node.

Taking the sequence 2pyrm 3rec 4je 5jue 9je 6je 8je 7 as an example, the binary heap structure established according to this algorithm is as follows:

{"value": 2, "left_child": {"value": 3, "left_child": {"value": 4, "left_child": {"value": 8, "left_child": null, "right_child": null} "right_child": {"value": 7, "left_child": null, "right_child": null}}, "right_child": {"value": 5, "left_child": null, "right_child": null} "right_child": {"value": 1, "left_child": {"value": 9, "left_child": null, "right_child": null}, "right_child": {"value": 6, "left_child": null "right_child": null} build a large top heap

On the basis of building the heap, there is a requirement that the value of the root node is larger than that of any node in the left and right subtree. Then the process of building a tree can be divided into two steps. For each value, first, according to the tree-building process, you will go to the bottom of the binary heap, and then by constantly comparing yourself with your root node, if you are larger than the root node, you can exchange your position with the root node and backtrack it recursively.

Logical process

Suppose that the red node is already a large top heap, and now a new node is added to the binary heap, and it is larger than any node, then the black arrow will be the action route of the node, and it will repeatedly compare with the parent. If it is greater than the parent, then swap the relationship with the parent.

The program implements public static BinaryHeap up (BinaryHeap father) {if (Objects.nonNull (father.getLeftChild () {if (father.getValue ())

< father.getLeftChild().getValue()) { int c = father.getValue(); father.setValue(father.getLeftChild().getValue()); father.getLeftChild().setValue(c); } up(father.getLeftChild()); } if (Objects.nonNull(father.getRightChild())) { if (father.getValue() < father.getRightChild().getValue()) { int c = father.getValue(); father.setValue(father.getRightChild().getValue()); father.getRightChild().setValue(c); } up(father.getRightChild()); } return father;} 该方法放在普通建树方法之后，就是大顶堆的建树方法了，总的方法如下： public static BinaryHeap bigPush(BinaryHeap binaryHeap, Integer value) { binaryHeap = buildHeap(binaryHeap, value); up(binaryHeap); return binaryHeap;} 还是以序列2,3,4,5,9,6,8,7为例，按照该算法建立出来的大顶堆结构如下： { "value": 9, "left_child": { "value": 8, "left_child": { "value": 7, "left_child": { "value": 2, "left_child": null, "right_child": null }, "right_child": { "value": 4, "left_child": null, "right_child": null } }, "right_child": { "value": 3, "left_child": null, "right_child": null } }, "right_child": { "value": 6, "left_child": { "value": 1, "left_child": null, "right_child": null }, "right_child": { "value": 5, "left_child": null, "right_child": null } }}建立小顶堆 小顶堆与大顶堆类似 逻辑过程 过程与大顶堆一致，不过此时是比父级小就和父级交换。 程序实现public static BinaryHeap down(BinaryHeap father) { if (Objects.nonNull(father.getLeftChild())) { if (father.getValue() >

Father.getLeftChild () .getValue () {int c = father.getValue (); father.setValue (father.getLeftChild () .getValue ()); father.getLeftChild () .setValue (c);} down (father.getLeftChild ()) } if (Objects.nonNull (father.getRightChild () {if (father.getValue () > father.getRightChild (). GetValue ()) {int c = father.getValue (); father.setValue (father.getRightChild (). GetValue ()); father.getRightChild (). SetValue (c);} down (father.getRightChild ());} return father;}

This is the process of going down, and the final code is:

Public static BinaryHeap smallPush (BinaryHeap binaryHeap, Integer value) {binaryHeap = buildHeap (binaryHeap, value); down (binaryHeap); return binaryHeap;}

Taking the sequence 2pyrum, 3pence4, 5joggle, 9jor6, 8, as an example, the structure of the small top stack built according to this algorithm is as follows:

{"value": 1, "left_child": {"value": 3, "left_child": {"value": 4, "left_child": {"value": 8, "left_child": null, "right_child": null} "right_child": {"value": 7, "left_child": null, "right_child": null}}, "right_child": {"value": 5, "left_child": null, "right_child": null} "right_child": {"value": 2, "left_child": {"value": 9, "left_child": null, "right_child": null}, "right_child": {"value": 6, "left_child": null "right_child": null} fetches data from the top of the heap and reconstructs the size top public static Integer bigPop (BinaryHeap binaryHeap) {Integer val = binaryHeap.getValue () If (binaryHeap.getLeftChild (). GetValue () > = binaryHeap.getRightChild (). GetValue ()) {binaryHeap.setValue (binaryHeap.getLeftChild (). GetValue ()); BinaryHeap binaryHeap1 = mergeTree (binaryHeap.getLeftChild (). GetLeftChild (), binaryHeap.getLeftChild (). GetRightChild ()); up (binaryHeap1); binaryHeap.setLeftChild (binaryHeap1);} else {binaryHeap.setValue (binaryHeap.getRightChild (). GetValue ()) BinaryHeap binaryHeap1 = mergeTree (binaryHeap.getRightChild (). GetLeftChild (), binaryHeap.getRightChild (). GetRightChild ()); up (binaryHeap1); binaryHeap.setRightChild (binaryHeap1);} return val;} public static Integer smallPop (BinaryHeap binaryHeap) {Integer val = binaryHeap.getValue (); if (binaryHeap.getLeftChild (). GetValue ()

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.