Maximum stack
The biggest heap is that the parent element is larger than the child element and is a completely binary tree.
data[1] starts to save, data[0] is empty and not used. You can also use data[0] as size.
public class MaxHeap<T extends Comparable<? super T>> {private T[] data;private int size;private int capacity;public MaxHeap(int capacity) {this.data = (T[]) new Comparable[capacity + 1];size = 0;this.capacity = capacity;}public int size() {return this.size;}public Boolean isEmpty() {return size == 0;}public int getCapacity() {return this.capacity;}/** * @return View the maximum root (only see it without deletion, compared with popMax) */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);}/** * @return Pop the maximum root (popup means deletion, compared with seekMax) */public T popMax() {swap(1, size--);shiftDown(1);return data[size + 1];}/** * @param child The lower corner mark of the child node is child, and the lower corner table of the parent node is child/2 */public void shiftUp(int child) {while (child > 1 && data[child].compareTo(data[child / 2]) > 0) {swap(child, child / 2);child = 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 the lower corner mark of which element is large*/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 lower corner mark of an element in the data array* @return Return the lower corner mark of which element is large*/private int max(int a, int b, int c) {int biggest = max(a, b);biggest = max(biggest, c);return bigger;}/** * @param father The lower corner mark of the parent node is father, and the lower corner tables of the left and right child nodes are: father*2 and father*2+1 */public void shiftDown(int father) {while (true) {int lchild = father * 2;//left child int rchild = father * 2 + 1;//right child int newFather = father;//newFather is about to be updated. Who is the lower corner mark of the parent, left and right nodes? If (lchild > size) {//If the father node has neither the left child nor the right child return;} else if (rchild > size) {//If the father node has only the left child, no right child newFather = max(father, lchild);} else {//If the father node has both the left child and the right child newFather = max(father, lchild, rchild);}if (newFather == father) {//It means that father is larger than both child nodes, and the table name is already a big root heap, so there is no need to continue to adjust the return;} else {// Otherwise, you need to continue to adjust the heap until the big root heap condition is met swap(father, newFather);//Values are swap = newFather;//Update the value of father, which is equivalent to continuing to adjust shiftDown(newFather)}}} public static void main(String[] args) {//Create a large root heap MaxHeap<Integer> maxHeap = new MaxHeap<Integer>(100);//Save for (int i = 0; i < 100; i++) {maxHeap.insert((int) (Math.random() * 100));}//Create an array Integer[] arr = new Integer[100];//Pick from the heap and put it into the array for (int i = 0; i < 100; i++) {arr[i] = maxHeap.popMax();System.out.print(arr[i] + " ");}System.out.println();}}Maximum heap: shiftDown() function is different from the above
public class MaxHeap<T extends Comparable<? super T>> {private T[] data;private int size;private int capacity;public MaxHeap(int capacity) {data = (T[]) new Comparable[capacity + 1];this.capacity = capacity;size = 0;}public int size() {return size;}public Boolean isEmpty() {return size == 0;}public void insert(T item) {data[size + 1] = item;size++;shiftUp(size);}/** * @return Pop Max root (pop-up means deletion, compared with seekMax) */public T popMax() {T ret = data[1];swap(1, size);size--;shiftDown(1);return ret;}/** * @return View the maximum root (only view without deletion, compared with popMax) */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 shiftUp(int k) {while (k > 1 && data[k / 2].compareTo(data[k]) < 0) {swap(k, k / 2);k /= 2;}}public void shiftDown(int father) {while (2 * father <= size) {int newFather = 2 * father;if (newFather + 1 <= size && data[newFather + 1].compareTo(data[newFather]) > 0) {//data[j] data[j+1] The one that takes the big newFather = newFather + 1;}if (data[father].compareTo(data[newFather]) >= 0) {break;} else {swap(father, newFather);//The value is exchanged father = newFather;//newFather is (2*father) or (2*father+1), that is, shiftDown(newFather);}}} public static void main(String[] args) {//Create a large root heap MaxHeap<Integer> maxHeap = new MaxHeap<Integer>(100);//Save for (int i = 0; i < 100; i++) {maxHeap.insert((int) (Math.random() * 100));}//Create an array Integer[] arr = new Integer[100];//Pick from the heap and put it into the array for (int i = 0; i < 100; i++) {arr[i] = maxHeap.popMax();System.out.print(arr[i] + " ");}System.out.println();}}Summarize
The above is all about the example of the Java language implementation maximum heap code, and 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!