The Java language implements the largest code sample

The maximum heap

The largest heap is characterized by the parent being larger than the child, and having a complete two-tree.

data[1] starts saving, data[0] is empty. 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 ( Can't delete ,  with popMax contrast )
   */
	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  Maximum pop root ( Pop up means delete ,  with seekMax contrast )
   */
	public T popMax() {
		swap(1, size--);
		shiftDown(1);
		return data[size + 1];
	}
	/**
   * @param child  The child node subscript is child , the parent node is the lower corner table 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 data The subscript of an element in an array 
   * @param b data The subscript of an element in an array 
   * @return  Returns the subscript 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 data The subscript of an element in an array 
   * @param b data The subscript of an element in an array 
   * @param c data The subscript of an element in an array 
   * @return  Returns the subscript 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;
	}
	/**
   * @param father  The parent node subscript is father, The lower corner table of the left and right child nodes is as follows: father*2  and  father*2+1
   */
	public void shiftDown(int father) {
		while (true) {
			int lchild = father * 2;
			// Left the child 
			int rchild = father * 2 + 1;
			// The right child 
			int newFather = father;
			//newFather About to update, father, left, right 3 Which node is bigger, newFather Whose subscript 
			if (lchild > size) {
				// If the father The node has neither left nor right children 
				return;
			} else if (rchild > size) {
				// If the father Nodes have only left children, no right children 
				newFather = max(father, lchild);
			} else {
				// If the father The node has both left children and right children 
				newFather = max(father, lchild, rchild);
			}
			if (newFather == father) {
				// instructions father It's bigger than the two children, and the table name is already a big root heap, so you don't have to adjust it any more 
				return;
			} else {
				// Otherwise, you need to continue tuning the heap until the large root heap condition is satisfied 
				swap(father, newFather);
				// Exchange values 
				father = newFather;
				// update father 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);
		// To the heap 
		for (int i = 0; i < 100; i++) {
			maxHeap.insert((int) (Math.random() * 100));
		}
		// Create an array 
		Integer[] arr = new Integer[100];
		// Take it out of the heap, put it in the array 
		for (int i = 0; i < 100; i++) {
			arr[i] = maxHeap.popMax();
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}
}

The shiftDown() function is not the same as 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  Maximum pop root ( Pop up means delete ,  with seekMax contrast )
   */
	public T popMax() {
		T ret = data[1];
		swap(1, size);
		size--;
		shiftDown(1);
		return ret;
	}
	/**
   * @return  View the maximum root ( Can't delete ,  with popMax contrast )
   */
	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] Take the larger of the two 
				newFather = newFather + 1;
			}
			if (data[father].compareTo(data[newFather]) >= 0) {
				break;
			} else {
				swap(father, newFather);
				// Exchange values 
				father = newFather;
				//newFather is (2*father) Or is it (2*father+1), Which is to go on shiftDown(newFather);
			}
		}
	}
	public static void main(String[] args) {
		// Create a large root heap 
		MaxHeap<Integer> maxHeap = new MaxHeap<Integer>(100);
		// To the heap 
		for (int i = 0; i < 100; i++) {
			maxHeap.insert((int) (Math.random() * 100));
		}
		// Create an array 
		Integer[] arr = new Integer[100];
		// Take it out of the heap, put it in the array 
		for (int i = 0; i < 100; i++) {
			arr[i] = maxHeap.popMax();
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}
}

conclusion

That's it for the most extensive code examples of Java language implementations in this article, and I hope you found them helpful. Interested friends can continue to refer to other related topics in this site, if there is any deficiency, welcome to comment out. Thank you for your support!