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

This article mainly introduces the relevant knowledge of how to write Java heap code, the content is detailed and easy to understand, the operation is simple and fast, and it has a certain reference value. I believe you will gain something after reading this Java heap code how to write an article. Let's take a look.

1. Definition of heap

①, which is a complete binary tree, every layer of the tree is full from left to right except that the last layer of the tree node does not need to be full. Pay attention to the following two cases, the second kind of last layer has a partition from left to right, so it is also an incomplete binary tree.

②, which is usually implemented as an array.

For this binary tree implemented with an array, assuming that the index value of the node is index, then:

The left child of the node is 2*index+1

The right child of the node is 2*index+2

The parent of the node is (index-1) / 2.

③, the keywords of each node in the heap are greater than (or equal to) the keywords of the child nodes of this node.

Here, we should pay attention to the difference between the heap and the previous binary search tree. The keywords of the left child nodes of all nodes in the binary search tree are smaller than those of the right child nodes. In the binary search tree, nodes can be traversed sequentially through a simple algorithm. But in the heap, it is difficult to traverse the nodes sequentially. As shown in the figure above, the heap is only arranged in descending order along each path from the root node to the leaf node. The left or right node of the specified node, and the upper node or lower node may have larger or smaller keywords than the specified node because they are not on the same path. Therefore, compared with the binary search tree, the heap is weakly ordered.

2. Traversal and lookup

As we said earlier, the heap is weakly ordered, so it is difficult to traverse the heap. Basically, the heap does not support traversal.

For lookup, because of the characteristics of the heap, there is not enough information to decide which of the two child nodes of the node to go to the next layer, so it is difficult to find a keyword in the heap.

As a result, the organization of the heap seems to be very close to disorder, but these two operations are sufficient for quickly removing the largest (or smallest) node, the root node, and for quickly inserting new nodes.

3. Remove

Remove refers to deleting the node with the largest (or smallest) keyword, that is, the root node.

The index of the root node in the array is always 0, that is, maxNode = heapArray [0]

After removing the root node, the tree has an empty root node, that is, the array has an empty data unit, which we have to fill in.

The first method is to move all the data items of the array forward one cell, which is time-consuming.

The second method:

①, remove Root

②, move the last node to the root location

③, filter this node down until it is below a node that is larger than it and above a node that is smaller than it.

The specific steps are as follows:

Figure a shows moving the last node to the root node, figures b, c, d show that the node is filtered down to the right location, its appropriate location is at the bottom (sometimes in the middle), and figure e shows the situation where the node is in the right location.

Note: when filtering down, compare the target node with its child nodes, and swap places with those who are older.

4. Insert

It is also easy to insert a node, selecting to filter up when inserting, initially inserting the node into the first empty cell at the end of the array, increasing the size of the array by one. Then carry on the algorithm of upward filtering.

Note: upward filtering is different from downward filtering. Upward filtering only needs to be compared with a parent node, and filtering stops when it is smaller than the parent node.

5. Complete Java heap code

First of all, we need to know some of the main points of representing the heap in arrays. If the index of the node in the array is x, then:

The left child of the node is 2*index+1

The right child of the node is 2*index+2

The parent of the node is (index-1) / 2.

Note: when the symbol "/" is applied to the expression of an integer, it performs integer division and gets a value that is rounded down.

Package com.ys.tree.heap; public class Heap {private Node [] heapArray; private int maxSize; private int currentSize; public Heap (int mx) {maxSize = mx; currentSize = 0; heapArray = new Node [maxSize];} public boolean isEmpty () {return (currentSize = = 0)? True: false;} public boolean isFull () {return (currentSize = = maxSize)? True: false;} public boolean insert (int key) {if (isFull ()) {return false;} Node newNode = newNode (key); heapArray [currentSize] = newNode; trickleUp (currentSize++); return true;} / / upward adjust public void trickleUp (int index) {int parent = (index-1) / 2 / / Index Node bottom of the parent node = heapArray [index]; / / store the newly added tail node in while in bottom (index > 0 & & heapArray [parent] .getKey ()

< bottom.getKey()) { heapArray[index] = heapArray[parent]; index = parent; parent = (parent - 1) / 2; } heapArray[index] = bottom; } public Node remove() { Node root = heapArray[0]; heapArray[0] = heapArray[--currentSize]; trickleDown(0); return root; } //向下调整 public void trickleDown(int index) { Node top = heapArray[index]; int largeChildIndex; while(index < currentSize/2) { //while node has at least one child int leftChildIndex = 2 * index + 1; int rightChildIndex = leftChildIndex + 1; //find larger child if(rightChildIndex < currentSize && //rightChild exists? heapArray[leftChildIndex].getKey() < heapArray[rightChildIndex].getKey()) { largeChildIndex = rightChildIndex; } else { largeChildIndex = leftChildIndex; } if(top.getKey() >

= heapArray [largeChildIndex] .getKey () {break;} heapArray [index] = heapArray [largeChildIndex]; index = largeChildIndex;} heapArray [index] = top;} / / change some data in the heap (int index, int newValue) {if (index) according to the index

< 0 || index >

= currentSize) {return false;} int oldValue = heapArray [index] .getKey (); heapArray [index] .setKey (newValue); if (oldValue < newValue) {trickleUp (index);} else {trickleDown (index);} return true } public void displayHeap () {System.out.println ("heapArray (array format):"); for (int I = 0; I < currentSize; iArray +) {if (heapArray [I]! = null) {System.out.print (heapArray [I] .getKey () + "") } else {System.out.print ("- -");} class Node {private int iData; public Node (int key) {iData = key;} public int getKey () {return iData;} public void setKey (int key) {iData = key }} this is the end of the article on "how to write Java heap code". Thank you for reading! I believe that everyone has a certain understanding of the knowledge of "how to write Java heap code". If you want to learn more, you are welcome to follow the industry information channel.

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.