最大堆
最大堆的特点是父元素比子元素大，并且是一棵完全二叉树。
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语言实现最大堆代码示例的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题，如有不足之处，欢迎留言指出。感谢朋友们对本站的支持！