本文主要是介绍大顶堆在Java中的一种优雅实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
既然小顶堆已经实现出来，那么同理大顶堆也顺理成章实现出来，只需稍微改动几个关键部分的代码。
/*** 大顶堆/最大堆实现* * @author stephenshen**/
public class MaxHeap {// 堆得存储结构：数组private int[] data;/*** 构造方法：传入一个数组，并转换为一个最大堆* * @param data*/public MaxHeap(int[] data) {this.data = data;buildHeap();}/*** 将数组转化为最大堆*/private void buildHeap() {//完全二叉树只有数组下标小于或等于 (data.length) / 2 - 1 的元素有孩子结点，遍历这些结点。//比如上面的图中，数组有10个元素， (data.length) / 2 - 1的值为4，a[4]有孩子结点，但a[5]没有//即，从下自上开始堆化（从最下层非叶子节点开始）for (int i = (data.length) / 2 - 1; i >= 0; i--) {heapify(i);}}/*** 从当前节点开始堆化* * @param i*/private void heapify(int i) {// 获取左右节点数组下标int l = left(i);int r = right(i);// 假定的当前节点、左子节点、右子节点中 最大值的下标int biggest = i;// 存在左子节点，且左子节点的值大于当前节点的值if (l < data.length && data[l] > data[i])biggest = l;// 存在右子节点，且右子节点的值大于当前节点的值if (r < data.length && data[r] > data[i])biggest = r;// 左右结点的值都小于根节点，直接returnif (i == biggest)return;// 将最大值与当前节点互换位置swap(i, biggest);// 从之前最大值节点位置重新堆化heapify(biggest);}/*** 获取右节点的数组下标* * @param i* @return*/private int right(int i) {return (i + 1) << 1;}/*** 获取左节点的数组下标* * @param i* @return*/private int left(int i) {return ((i + 1) << 1) - 1;}/*** 交换元素位置* * @param i* @param j*/private void swap(int i, int j) {int tmp = data[i];data[i] = data[j];data[j] = tmp;}/*** 获取堆中最大元素，即根元素* * @return*/public int getRoot() {return data[0];}/*** 替换根元素，并重新heapify* * @param root*/public void setRoot(int root) {data[0] = root;heapify(0);}
}这篇关于大顶堆在Java中的一种优雅实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
