以数组来存放堆数据
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); } }
以上就是关于算法设计与分析基之堆的示例的详细内容，更多请关注其它相关文章！
可你仍然感谢天地和人世所带来的这些变化和发生。
