以数组来存放堆数据
package cn.xf.algorithm.ch06changerule;
import java.util.arraylist;
import java.util.list;
import org.junit.test;
/**
*
* 功能：堆的构造
* 1、堆可以定义为一颗二叉树，树的节点包含键，并且满足一下条件
* 1） 树的形状要求：这棵二叉树是基本完备的（完全二叉树），树的每一层都是满的，除了最后一层最右边的元素可能缺位
* 2） 父母优势，堆特性，每一个节点的键都要大于或者等于他子女的键（对于任何叶子我们认为这都是自动满足的）
*
* 对于堆：
* 只存在一颗n个节点的完全二叉树他的高度:取下界的 log2的n的对数
* 堆的根总是包含了堆的最大元素
* 堆的一个节点以及该节点的子孙也是一个堆
* 可以用数组的来实现堆，方法是从上到下，从左到右的方式来记录堆的元素。
* @author xiaofeng
* @date 2017年7月9日
* @filename heap.java
*
*/
public class heap {
/**
* 堆的数据存放结构
*/
private list<double> heap;
/**
* 自下而上构建一个堆
*/
private list<double> createheaddowntoup(list<double> heap) {
if(heap == null || heap.size() <= 0)
return heap;
//数据个数
int nums = heap.size();
//吧数组整体后移一位，方便数据的计算，因为从0开始，那么2*0还是0，没有体现出2*n就是n的左孩子的基本设定
heap.add(0, 0d);
//构建一个堆，从数组的中间位置开始，因为中间位子mid的两倍正好差不多是这个树的末尾，而在这个2*mid的附近就是mid这个节点的孩子节点
for(int i = nums / 2 + 1; i > 0; --i) {
//获取基准节点的地址
int baseindex = i;
//获取这个节点的值
double vbasevalue = heap.get(baseindex);
boolean isheap = false; //这个用来判断当前遍历的这三个数字是否满足堆的概念
//进行堆变换，交换树的节点和孩子节点数值，使当前树满足堆的概念
//2 * baseindex <= nums 这个用来判断这颗树的子树也满足堆的定义
while(!isheap && 2 * baseindex <= nums) {
//获取当前遍历到的数据的左孩子节点的位置
int maxchildindex = 2 * baseindex;
//从两个孩子节点中获取大的那个位置
if(maxchildindex < nums) {
//如果左孩子的位置比总长还小，由于完全二叉树的属性，那么必定存在右孩子节点
//判断那个孩子节点的数据比较大，使max为大的那个
if(heap.get(maxchildindex) < heap.get(maxchildindex + 1)) {
//如果右孩子比较大
maxchildindex += 1;
}
}
//再判断，当前 节点的值是不是比孩子节点的值要大，如果是那么就当前子树是满足堆的属性
//maxchildindex == nums 那还是瞒住条件，可以进行左子树的比较
if(maxchildindex > nums || vbasevalue >= heap.get(maxchildindex)) {
isheap = true;
} else {
//如果不满住，那么交换，吧大的数据交换到节点上，吧节点的数据换到孩子节点上
heap.set(baseindex, heap.get(maxchildindex));
baseindex = maxchildindex;
heap.set(baseindex, vbasevalue);
}
}
}
//去除第一个0，然后返回
heap.remove(0);
return heap;
}
private void shifheaddowntoup(int i) {
if (heap == null || heap.size() <= 0)
return;
// 数据个数
int nums = heap.size();
// 吧数组整体后移一位，方便数据的计算，因为从0开始，那么2*0还是0，没有体现出2*n就是n的左孩子的基本设定
heap.add(0, 0d);
boolean isheap = false;
int baseindex = i;
double vbasevalue = heap.get(i);
while (!isheap && 2 * baseindex <= nums) {
// 获取当前遍历到的数据的左孩子节点的位置
int maxchildindex = 2 * baseindex;
// 从两个孩子节点中获取大的那个位置
if (maxchildindex < nums) {
// 如果左孩子的位置比总长还小，由于完全二叉树的属性，那么必定存在右孩子节点
// 判断那个孩子节点的数据比较大，使max为大的那个
if (heap.get(maxchildindex) < heap.get(maxchildindex + 1)) {
// 如果右孩子比较大
maxchildindex += 1;
}
}
// 再判断，当前 节点的值是不是比孩子节点的值要大，如果是那么就当前子树是满足堆的属性
// maxchildindex == nums 那还是瞒住条件，可以进行左子树的比较
if (maxchildindex > nums || vbasevalue >= heap.get(maxchildindex)) {
isheap = true;
} else {
// 如果不满住，那么交换，吧大的数据交换到节点上，吧节点的数据换到孩子节点上
heap.set(baseindex, heap.get(maxchildindex));
baseindex = maxchildindex;
heap.set(baseindex, vbasevalue);
}
}
// 去除第一个0，然后返回
heap.remove(0);
}
//创建堆
public heap() {
heap = new arraylist<double>();
createheaddowntoup(heap);
}
public heap(list<double> data) {
if(data == null || data.size() <= 0) {
data = new arraylist<double>();
}
heap = data;
createheaddowntoup(heap);
}
@override
public string tostring() {
return heap.tostring();
}
public void add(double value) {
if(value == null)
return;
heap.add(value);
// int insertinedx = heap.size();
//自底向上构建堆
for(int i = heap.size() / 2; i >= 0; --i) {
shifheaddowntoup(i + 1);
}
}
/**
* 删除一个元素，获取这个元素的索引位置来删除
* 1、根的键《和》堆的最后一个键k做交换
* 2、堆的规模减一
* 3、严格按照自底向上的够着算法的做法，吧k 向下筛选，堆数据进行堆化
* @param index
*/
public void delete(int index) {
//这个是自底向上进行堆化数据
//吧最后一个数据填入到要删除的数据中
double lastvalue = heap.get(heap.size() - 1);
//删除最后一个元素，吧最后一个元素用来取代这个需要删除的元素
heap.set(index, lastvalue);
heap.remove(heap.size() - 1);
//自底向上开始堆化
for(int i = index; i >= 0; --i)
shifheaddowntoup(i + 1);
}
}
以上就是关于算法设计与分析基之堆的示例的详细内容。