A binary heap is a special heap. A binary heap is a complete binary tree (binary tree) or an approximately complete binary tree (binary tree). There are two types of binary heaps: the largest heap and the smallest heap. Maximum heap: The key value of the parent node is always greater than or equal to the key value of any child node; Minimum heap: The key value of the parent node is always less than or equal to the key value of any child node.
Print binary heap: utilize hierarchical relationships
Here I first sort the heap, and then execute the method to print the heap in sort printAsTree()
public class MaxHeap<T extends Comparable<? super T>> { private T[] data; private int size; private int capacity; public MaxHeap(int capacity) { this.capacity = capacity; this.size = 0; this.data = (T[]) new Comparable[capacity + 1]; } public MaxHeap(T[] arr) {//heapify, array heap capacity = arr.length; data = (T[]) new Comparable[capacity + 1]; System.arraycopy(arr, 0, data, 1, arr.length); size = arr.length; for (int i = size / 2; i >= 1; i--) { shiftDown(i); } } public int size() { return this.size; } public int getCapacity() { return this.capacity; } public boolean isEmpty() { return size == 0; } public T seekMax() { return data[1]; } public void swap(int i, int j) { if (i != j) { T temp = data[i]; data[i] = data[j]; data[j] = temp; } } public void insert(T item) { size++; data[size] = item; shiftUp(size); } public T popMax() { swap(1, size--); shiftDown(1); return data[size + 1]; } public void shiftUp(int child) { while (child > 1 && data[child].compareTo(data[child / 2]) > 0) { swap(child, child / 2); child /= 2; } } /** * @param a lower corner mark of an element in the data array* @param b lower corner mark of an element in the data array* @return Return which element is larger, the lower corner mark of which element is larger*/ private int max(int a, int b) { if (data[a].compareTo(data[b]) < 0) {//If data[b] big return b;//Return b } else {//If data[a] big return a;//Return a } } /** * @param a lower corner mark of an element in the data array* @param b lower corner mark of an element in the data array* @param c The lower corner mark of an element in the data array* @return The lower corner mark of which element is larger*/ private int max(int a, int b, int c) { int biggest = max(a, b); biggest = max(biggest, c); return biggest; } public void shiftDown(int father) { while (true) { int lchild = father * 2; int rchild = father * 2 + 1; int newFather = father;//It doesn't matter whether the assignment is assigned here. If the following return is changed to break, it must be assigned if (lchild > size) {//If there is no left and right children return; } else if (rchild > size) {//If there is no right child newFather = max(father, lchild); } else {//If there is a left and right children newFather = max(father, lchild, rchild); } if (newFather == father) {//If the original parent node is the largest of three, you don't need to continue to sort out the pile return; } else {//The parent node is not the largest, swap the older children and continue to adjust the downwards until the large root heap is satisfied swap(newFather, father); father = newFather;//Equivalent to shiftDown(newFather). If newFather turns out to be the left child of father, it is equivalent to shiftDown(2*father) } } } public static <T extends Comparable<? super T>> void sort(T[] arr) { int len = arr.length; MaxHeap<T> maxHeap = new MaxHeap<>(arr); maxHeap.printAsTree(); for (int i = len - 1; i >= 0; i--) { arr[i] = maxHeap.popMax(); } } public static void printArr(Object[] arr) { for (Object o : arr) { System.out.print(o); System.out.print("/t"); } System.out.println(); } public void printSpace(int n) {//Print n spaces (used with '/t' here instead) for (int i = 0; i < n; i++) { System.out.printf("%3s", ""); } } public void printAsTree() { int lineNum = 1;//First traverse the first line int lines = (int) (Math.log(size) / Math.log(2)) + 1;//lines is the number of layers of the heap int spaceNum = (int) (Math.pow(2, lines) - 1); for (int i = 1; i <= size; ) { //Because data is stored in the left and right closed interval in [1...size], data[0] does not store data//Each layer prints this interval [2^(layer number-1) ... (2^layer number)-1]. If the number in the heap is not enough (2^ layers)-1, print to size. So take min((2^ layers)-1,size). for (int j = (int) Math.pow(2, lineNum - 1); j <= Math.min(size, (int) Math.pow(2, lineNum) - 1); j++) { printSpace(spaceNum); //Print spaces with spaceNum System.out.printf("%3s", data[j]); //Print data System.out.printf("%3s", ""); //Green box in the picture printSpace(spaceNum); //Print spaces with spaceNum i++; //Every element is printed, it is + 1 } lineNum++; spaceNum = spaceNum / 2; System.out.println(); } } public static void main(String args[]) { Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6, 1, 3, 6, 1, 1}; sort(arr); }}Execution results:
Summarize
The above is all the content of this article about the printing code sharing of the Java language that implements binary heaps. I hope it will be helpful to everyone. Interested friends can continue to refer to other related topics on this site. If there are any shortcomings, please leave a message to point it out. Thank you friends for your support for this site!