堆结构(heap)
生活中我们遇见的数据结构-堆： 查看电影口碑排名第一的电影。
堆的概念
[堆(heap)] 是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：
- 堆中某个结点的值总是不大于或不小于其父结点的值；
- 堆总是一棵完全二叉树。
**[完全二叉树] **若设二叉树的深度为h，除第h层外，其它各层 (1～h-1)的结点数都达到最大个数，第h层所有的结点都连续集中在最左边，这就是完全二叉树。
堆的性质
堆的类型
堆从根节点的大小可以分为最大堆和最小堆
[最大堆] : always greater than its child node/s and the key of the root node is the largest among all other nodes. This property is also called max heap property.
[最小堆] :always smaller than the child node/s and the key of the root node is the smallest among all other nodes. This property is also called min heap property.
最大堆：根结点最大的堆叫做最大堆或大根堆
最小堆：根结点最小的堆叫做最小堆或小根堆
堆的性质
根节点 没有父亲节点 --> root.parent = null;
节点和数组的索引之间的关系，假设数组的索引为(i), parent表示堆的父节点索引, leftIndex：左节点索引, rightIndex:有节点索引：
- 父节点索引: parent = (i-1)/2
- 左子节点索引: leftIndex = parent *2 +1;
- 右子节点索引: rightIndex = parent * 2 +1;
构建堆
堆类的基本构成
数组与树的对应关系
根据数组中索引与树中的父节点，左子节点、右子节点之间的对应关系。
根节点索引 = (数组索引-1) /2
左子节点索引 = 2 * (父节点索引) + 1;
构建获取父节点索引和子节点索引的辅助方法。
/**
* 根据数组索引值获取堆的父节点索引
* @param index 当前数组的索引值
* @return
*/
public int getParentIndex(int index) {
return index <= 0 ? -1 : (index - 1) / 2;
}
/**
* 根据父节点索引获取左子节点的索引值
* @param parentIndex 父节点索引
* @return
*/
public int getLeftIndex(int parentIndex){
return 2 * parentIndex + 1;
}
添加数据
添加数据需要进行上浮(floatUp)操作。如下图堆中要新添加数据60。
查找要挂载的父节点
挂载节点到父节点
public void add(int val){
elements[size++] = val; //挂载数据
//上浮操作
}
新节点进行上浮操作
获取当前数组索引对应的父节点索引
int parentIndex = getParentIndex(currIndex);
交换父子节点
检查新加入的节点是否比父节点大，如果大则交换两个节点的值
private void swap(int i, int j) {
T tmp = elements[i];
elements[i] = elements[j];
elements[j] = tmp;
}
while(parentIndex != -1 && elements[parentIndex] < elements[currIndex]){
swap(currIndex, parentIndex);
.....
}
遍历交换
由于可能新节点交换后会大于新的父节点，那么要依次进行调整。
private void floatUp(int currIndex) {
.......
currIndex = parentIndex;
parentIndex = getParentIndex(currIndex);
........
}
添加节点(完整代码)
private void swap(int i, int j) {
T tmp = elements[i];
elements[i] = elements[j];
elements[j] = tmp;
}
private void floatUp(int currIndex) {
while(parentIndex != -1 && elements[parentIndex] < elements[currIndex]){
swap(currIndex, parentIndex);
currIndex = parentIndex;
parentIndex = getParentIndex(currIndex);
}
}
public void add(int val){
elements[size++] = val; //挂载数据
//上浮操作
floatUp(size-1);
}
下沉操作(删除)
以最大堆为例，删除最大堆的根节点。
非空判断
public boolean isEmpty(){
return size == 0;
}
判断堆是否为空
如果堆为空则，删除失败
if (isEmpty()) {
return null;
}
找到要删除的堆元素
要删除的堆的最大值，即堆的第一个元素elements[0];
if (isEmpty()) return null;
int wanted = elements[0];
交换数据
使用最后一个元素替换要删除的元素，将堆的容量进行-1操作。
elements[0] = elements[size-1];
size--;
下沉操作 (swingDown)
最后一个元素(25)移动到了root位置，不符合最大堆的条件，需要将根节点(elements[0])下沉到合适的位置操作。
记录要删除的值，记录当前位置，找到其左子节点
int swimElement = elements[currIndex];
int leftIndex = getLeftIndex(currIndex);
条件： 左节点的索引没到堆末尾
while(leftIndex < size){
:
:
}
查找左、右子节点中最大值的索引
定义最高节点值的索引: highIndex
int highIndex = leftIndex; //初始化为左节点索引获取右节点索引
int rightIndex = leftIndex + 1;判断左右节点的最大值，更新highIndex
if (leftIndex < size && elements[rightIndex] > elements[leftIndex]) { highIndex = rightIndex; }
highIndex 值与当前要删除的swim值比较
如果左、右子树的值大于swimVal，则交换节点值。
if (swimElement < elements[highIndex]) {
swap(highIndex, currIndex);
currIndex = highIndex;
leftIndex = getLeftIndex(currIndex);
} else {
break;
}
下沉（完整代码)
根据当前节点进行下沉操作
private void swimDown(int currIndex) {
int swimElement = elements[currIndex];
int leftIndex = getLeftIndex(currIndex);
while (leftIndex < size) {
int highIndex = leftIndex;
int rightIndex = leftIndex + 1;
if (leftIndex < size && elements[rightIndex] > elements[leftIndex]) {
highIndex = rightIndex;
}
if (swimElement < elements[highIndex]) {
swap(highIndex, currIndex);
currIndex = highIndex;
leftIndex = getLeftIndex(currIndex);
} else {
break;
}
}
}
删除堆的顶根节点元素
public Integer remove() {
if (isEmpty()) return null;
int wanted = elements[0];
//更新根节点
elements[0] = elements[size - 1];
size--;
swimDown(0);
return wanted;
}