关于算法设计与分析基之堆的示例

以数组来存放堆数据

《PHP设计模式指南》中文版

《PHP设计模式》首先介绍了设计模式，讲述了设计模式的使用及重要性，并且详细说明了应用设计模式的场合。接下来，本书通过代码示例介绍了许多设计模式。最后，本书通过全面深入的案例分析说明了如何使用设计模式来计划新的应用程序，如何采用PHP语言编写这些模式，以及如何使用书中介绍的设计模式修正和重构已有的代码块。作者采用专业的、便于使用的格式来介绍相关的概念，自学成才的编程人员与经过更多正规培训的编程人员

下载

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 heap;
 
    /**
     * 自下而上构建一个堆
     */
    private List createHeadDownToUp(List 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();
        createHeadDownToUp(heap);
    }
     
    public Heap(List data) {
        if(data == null || data.size() <= 0) {
            data = new ArrayList();
        }
        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);
    }
     
}