数据结构之二叉堆
一、什么是二叉堆
二叉堆是一种特殊的堆，二叉堆是完全二元树（二叉树）或者是近似完全二元树（二叉树）。
二叉堆有两种：最大堆和最小堆。
最大堆：父结点的键值总是大于或等于任何一个子节点的键值；
最小堆：父结点的键值总是小于或等于任何一个子节点的键值。
二、二叉堆的基本操作
1.插入
假设在最大堆[90,80,70,60,40,30,20,10,50]种插入85，需要执行的步骤如下：
插入分为两步：
(1).将data添加到表尾
/*
* 将data插入到二叉堆中
*/
public void insert(T data) {
int size = mHeap.size();
mHeap.add(data); // 将"数组"插在表尾
filterup(size); // 向上调整堆
}
(2).调用向上调整算法
/*
* 最大堆的向上调整算法(从start开始向上直到0，调整堆)
*
* 注：数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
*
* 传入当前节点的索引start，然后(start-1)/2拿到它父节点的索引，将当前start节点记下来 比较它与父节点的大小，
* 若大于父节点，先将start节点值set为父节点的值，然后两个指针同步上移，（把父节点赋值给当前节点，父节点上移找父节点） 直到走到不满足start>0
* 将记下来的值set到新start处 参数说明： start -- 被上调节点的起始位置(一般为数组中最后一个元素的索引)
*/
protected void filterup(int start) {
int c = start; // 当前节点(current)的位置
int p = (c - 1) / 2; // 父(parent)结点的位置
T tmp = mHeap.get(c); // 当前节点(current)的大小
while (c > 0) {
int cmp = mHeap.get(p).compareTo(tmp);
if (cmp >= 0)
break;
else {
mHeap.set(c, mHeap.get(p));
c = p;
p = (p - 1) / 2;
}
}
mHeap.set(c, tmp);
}
2.删除
假设从最大堆[90,85,70,60,80,30,20,10,50,40]中删除90，需要执行的步骤如下：
也是分为两步：
（1）将data删除，把表尾最后一个元素放上来
/*
* 删除最大堆中的data
*
* 先将data删除，将最后一个元素放上来， 调用向下调算法
*
*
* 返回值： 0，成功 -1，失败
*/
public int remove(T data) {
if (mHeap.isEmpty()) {
return -1;
}
int index = mHeap.indexOf(data);
if (index == -1) {
return -1;
}
int size = mHeap.size();
mHeap.set(index, mHeap.get(size - 1));// size-1索引处的值是最后一个元素，将这个元素放到删除元素处
mHeap.remove(size - 1);// 把最后一个元素删除，然后调用向下调整算法
filterdown(index, mHeap.size() - 1);
return 0;
}
（2）调用向下调整算法
/*
* 最大堆的向下调整算法
*
* 注：数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
*
* 从start位置，向下找它最大的孩子，与它自己比较 如果孩子大于它，将此孩子值set到start位置 start下移 反复执行直至条件不满足
* 最后把初始start处的值set到新位置
*
*
* 参数说明： start -- 被下调节点的起始位置(一般为0，表示从第1个开始) end -- 截至范围(一般为数组中最后一个元素的索引)
*/
protected void filterdown(int start, int end) {
int c = start; // 当前(current)节点的位置
int l = 2 * c + 1; // 左(left)孩子的位置
T tmp = mHeap.get(c); // 当前(current)节点的大小
while (l <= end) {
int cmp = mHeap.get(l).compareTo(mHeap.get(l + 1)); // "l"是左孩子，"l+1"是右孩子
if (l < end && cmp < 0)
l++; // 左右两孩子中选择较大者，即mHeap[l+1]
cmp = tmp.compareTo(mHeap.get(l));
if (cmp >= 0)
break; // 调整结束
else {
mHeap.set(c, mHeap.get(l));
c = l;
l = 2 * l + 1;
}
}
mHeap.set(c, tmp);
}
下面是完整代码：
package priv.qcy.heap;
import java.util.ArrayList;
import java.util.List;
public class MaxHeap<T extends Comparable<T>> {
private List<T> mHeap; // 队列(实际上是动态数组ArrayList的实例)
public MaxHeap() {
this.mHeap = new ArrayList<T>();
}
/*
* 最大堆的向下调整算法
*
* 注：数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
*
* 从start位置，向下找它最大的孩子，与它自己比较 如果孩子大于它，将此孩子值set到start位置 start下移 反复执行直至条件不满足
* 最后把初始start处的值set到新位置
*
*
* 参数说明： start -- 被下调节点的起始位置(一般为0，表示从第1个开始) end -- 截至范围(一般为数组中最后一个元素的索引)
*/
protected void filterdown(int start, int end) {
int c = start; // 当前(current)节点的位置
int l = 2 * c + 1; // 左(left)孩子的位置
T tmp = mHeap.get(c); // 当前(current)节点的大小
while (l <= end) {
int cmp = mHeap.get(l).compareTo(mHeap.get(l + 1)); // "l"是左孩子，"l+1"是右孩子
if (l < end && cmp < 0)
l++; // 左右两孩子中选择较大者，即mHeap[l+1]
cmp = tmp.compareTo(mHeap.get(l));
if (cmp >= 0)
break; // 调整结束
else {
mHeap.set(c, mHeap.get(l));
c = l;
l = 2 * l + 1;
}
}
mHeap.set(c, tmp);
}
/*
* 删除最大堆中的data
*
* 先将data删除，将最后一个元素放上来， 调用向下调算法
*
*
* 返回值： 0，成功 -1，失败
*/
public int remove(T data) {
if (mHeap.isEmpty()) {
return -1;
}
int index = mHeap.indexOf(data);
if (index == -1) {
return -1;
}
int size = mHeap.size();
mHeap.set(index, mHeap.get(size - 1));// size-1索引处的值是最后一个元素，将这个元素放到删除元素处
mHeap.remove(size - 1);// 把最后一个元素删除，然后调用向下调整算法
filterdown(index, mHeap.size() - 1);
return 0;
}
/*
* 将data插入到二叉堆中
*/
public void insert(T data) {
int size = mHeap.size();
mHeap.add(data); // 将"数组"插在表尾
filterup(size); // 向上调整堆
}
/*
* 最大堆的向上调整算法(从start开始向上直到0，调整堆)
*
* 注：数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
*
* 传入当前节点的索引start，然后(start-1)/2拿到它父节点的索引，将当前start节点记下来 比较它与父节点的大小，
* 若大于父节点，先将start节点值set为父节点的值，然后两个指针同步上移，（把父节点赋值给当前节点，父节点上移找父节点） 直到走到不满足start>0
* 将记下来的值set到新start处 参数说明： start -- 被上调节点的起始位置(一般为数组中最后一个元素的索引)
*/
protected void filterup(int start) {
int c = start; // 当前节点(current)的位置
int p = (c - 1) / 2; // 父(parent)结点的位置
T tmp = mHeap.get(c); // 当前节点(current)的大小
while (c > 0) {
int cmp = mHeap.get(p).compareTo(tmp);
if (cmp >= 0)
break;
else {
mHeap.set(c, mHeap.get(p));
c = p;
p = (p - 1) / 2;
}
}
mHeap.set(c, tmp);
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < mHeap.size(); i++)
sb.append(mHeap.get(i) + " ");
return sb.toString();
}
public static void main(String[] args) {
int i;
int a[] = { 10, 40, 30, 60, 90, 70, 20, 50, 80 };
MaxHeap<Integer> tree = new MaxHeap<Integer>();
System.out.printf("== 依次添加: ");
for (i = 0; i < a.length; i++) {
System.out.printf("%d ", a[i]);
tree.insert(a[i]);
}
System.out.printf("\n== 最 大 堆: %s", tree);
i = 85;
tree.insert(i);
System.out.printf("\n== 添加元素: %d", i);
System.out.printf("\n== 最 大 堆: %s", tree);
i = 90;
tree.remove(i);
System.out.printf("\n== 删除元素: %d", i);
System.out.printf("\n== 最 大 堆: %s", tree);
System.out.printf("\n");
}
}
运行结果：
emmmmm仅供个人复习所用，如有错误欢迎指正！