最大堆
最大堆的特點是父元素比子元素大，並且是一棵完全二叉樹。
data[1]開始存，data[0]空著不用。也可以把data[0]當成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 查看最大根(只看不刪, 與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 彈出最大根(彈出意味著刪除, 與seekMax對比) */public T popMax() {swap(1, size--);shiftDown(1);return data[size + 1];}/** * @param child 孩子節點下角標是child，父節點下角表是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數組中某個元素的下角標* @param b data數組中某個元素的下角標* @return 哪個元素大就返回哪個的下角標*/private int max(int a, int b) {if (data[a].compareTo(data[b]) < 0) {//如果data[b]大return b;//返回b} else {//如果data[a]大return a;//返回a}}/** * @param a data數組中某個元素的下角標* @param b data數組中某個元素的下角標* @param c data數組中某個元素的下角標* @return 哪個元素大就返回哪個的下角標*/private int max(int a, int b, int c) {int biggest = max(a, b);biggest = max(biggest, c);return biggest;}/** * @param father 父節點下角標是father,左右兩個孩子節點的下角表分別是：father*2 和father*2+1 */public void shiftDown(int father) {while (true) {int lchild = father * 2;//左孩子int rchild = father * 2 + 1;//右孩子int newFather = father;//newFather即將更新，父、左、右三個結點誰大，newFather就是誰的下角標if (lchild > size) {//如果該father結點既沒有左孩子，也沒有右孩子return;} else if (rchild > size) {//如果該father結點只有左孩子，沒有右孩子newFather = max(father, lchild);} else {//如果該father結點既有左孩子，又有右孩子newFather = max(father, lchild, rchild);}if (newFather == father) {//說明father比兩個子結點都要大，表名已經是大根堆，不用繼續調整了return;} else {//否則，還需要繼續調整堆，直到滿足大根堆條件為止swap(father, newFather);//值進行交換father = newFather;//更新father的值，相當於繼續調整shiftDown(newFather)}}}public static void main(String[] args) {//創建大根堆MaxHeap<Integer> maxHeap = new MaxHeap<Integer>(100);//向堆裡存for (int i = 0; i < 100; i++) {maxHeap.insert((int) (Math.random() * 100));}//創建數組Integer[] arr = new Integer[100];//從堆裡取，放進數組裡for (int i = 0; i < 100; i++) {arr[i] = maxHeap.popMax();System.out.print(arr[i] + " ");}System.out.println();}}最大堆：shiftDown()函數與上面不一樣
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 彈出最大根(彈出意味著刪除, 與seekMax對比) */public T popMax() {T ret = data[1];swap(1, size);size--;shiftDown(1);return ret;}/** * @return 查看最大根(只看不刪, 與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]兩者取大的那個newFather = newFather + 1;}if (data[father].compareTo(data[newFather]) >= 0) {break;} else {swap(father, newFather);//值進行交換father = newFather;//newFather是(2*father)或者是(2*father+1),也就是繼續shiftDown(newFather);}}}public static void main(String[] args) {//創建大根堆MaxHeap<Integer> maxHeap = new MaxHeap<Integer>(100);//向堆裡存for (int i = 0; i < 100; i++) {maxHeap.insert((int) (Math.random() * 100));}//創建數組Integer[] arr = new Integer[100];//從堆裡取，放進數組裡for (int i = 0; i < 100; i++) {arr[i] = maxHeap.popMax();System.out.print(arr[i] + " ");}System.out.println();}}總結
以上就是本文關於Java語言實現最大堆代碼示例的全部內容，希望對大家有所幫助。感興趣的朋友可以繼續參閱本站其他相關專題，如有不足之處，歡迎留言指出。感謝朋友們對本站的支持！