最大堆

最大堆的特点是父元素比子元素大，并且是一棵完全二叉树。

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