堆总是满足下列性质：
1、堆中某个节点的值总是不大于或不小于其父节点的值；
2、堆总是一棵完全二叉树。
应用：堆排序可以实现时间复杂度为nlogn
堆的基本操作
上浮 shift_up；
下沉 shift_down
插入 push
弹出 pop
取顶 top
堆排序 heap_sort
应用实例
PriorityQueue：优先队列，具备了小根堆的性质
public static int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
// 构建二维数数组并按照效率降序排序
int[][] arr = new int[n][2];
for (int i = 0; i < n; i++) {
arr[i][0] = speed[i];
arr[i][1] = efficiency[i];
}
// 按效率降排序
Arrays.sort(arr, (a, b) -> b[1] - a[1]);
// 小根堆
PriorityQueue<Integer> priorityQueue = new PriorityQueue();
long sum = 0;
long res = 0;
// 计算效率
for (int i = 0; i < n; i++) {
priorityQueue.add(arr[i][0]);
sum += arr[i][0];
// 当堆中的数据超过k时，将最小的移除
if (priorityQueue.size() > k) {
sum -= priorityQueue.poll();
}
res = Math.max(res, sum * arr[i][1]);
}
System.out.println("res:" + res);
return (int)(res % ((int)1e9 + 7));
}堆算法
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 二叉堆 二叉堆是一棵完全二叉树，且任意一个结点的键值总是小于或等于其子结点的键值（最小堆）。二叉堆采用数组来存储（...
