堆是一棵特殊的树，具有如下特点：
1. 完全二叉树。除了最后一层，每一层从左到右是满员的。
【#|排序 堆排序-基础篇】2. 每个节点都是大于或者等于它的子节点。
3. 通常由数组实现。
数组表示堆的时候，具有如下特性：
数组中的任意索引x
1. 父节点为(x - 1)/ 2
2. 左子节点为2*x+1
3. 右子节点为2*x+2
基础代码部分
/**这里我们将介绍插入堆尾时的向上shuai选。移除堆顶时的向下shuai选**/public void insert(int node) {
heapArray[currentSize] = node;
trickleUp(currentSize++);
}
public void trickleUp(int index) {
int parent = (index - 1) / 2;
int bottom = heapArray[index];
while(index > 0 && heapArray[parent] < bottom) {
heapArray[index] = heapArray[parent];
index = parent;
parent = (parent - 1) / 2;
}
heapArray[index] = bottom;
}public int remove() {
int root = heapArray[0];
heapArray[0] = heapArray[--currentSize];
trickleDown(0);
return root;
}
public void trickleDown(int index) {
int largerChild;
int top = heapArray[index];
while(index < currentSize / 2) {
int leftChild = 2*index + 1;
int rightChild = leftChild + 1;
if(rightChild < currentSize && heapArray[rightChild] > heapArray[leftChild]) {
largerChild = rightChild;
} else {
largerChild = leftChild;
}if(top >= heapArray[largerChild]) {
break;
}
heapArray[index] = heapArray[largerChild];
index = largerChild;
}
heapArray[index] = top;
}推荐阅读
- 人工智能|干货！人体姿态估计与运动预测
- 分析COMP122 The Caesar Cipher
- 技术|为参加2021年蓝桥杯Java软件开发大学B组细心整理常见基础知识、搜索和常用算法解析例题（持续更新...)
- C语言学习(bit)|16.C语言进阶——深度剖析数据在内存中的存储
- Python机器学习基础与进阶|Python机器学习--集成学习算法--XGBoost算法
- 数据结构与算法|【算法】力扣第 266场周赛
- 数据结构和算法|LeetCode 的正确使用方式
- leetcode|今天开始记录自己的力扣之路
- 人工智能|【机器学习】深度盘点（详细介绍 Python 中的 7 种交叉验证方法！）
- 网络|简单聊聊压缩网络