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 = http://www.mamicode.com/heap.get(baseIndex);>