package cn.xf.algorithm.ch09Greedy.util;
import java.util.ArrayList;
import java.util.List;
/**
* 堆构造以及排序
*
* .功能：堆的构造
* 1、堆可以定义为一颗二叉树，树的节点包含键，并且满足一下条件
* 1） 树的形状要求：这棵二叉树是基本完备的（完全二叉树），树的每一层都是满的，除了最后一层最右边的元素可能缺位
* 2） 父母优势，堆特性，每一个节点的键都要大于或者等于他子女的键（对于任何叶子我们认为这都是自动满足的）
*
* 对于堆：
* 只存在一颗n个节点的完全二叉树他的高度:取下界的 log2的n的对数
* 堆的根总是包含了堆的最大元素
* 堆的一个节点以及该节点的子孙也是一个堆
* 可以用数组的来实现堆，方法是从上到下，从左到右的方式来记录堆的元素。
*
* @author xiaof
* @version Revision 1.0.0
* @see:
* @创建日期：2017年8月25日
* @功能说明：
*
*/
public class Heap {
private List<Integer> heap;
//构造函数
public Heap() {
//创建堆
heap = new ArrayList<Integer>();
}
public Heap(List<Integer> heap) {
//创建堆
this.heap = heap;
createHeadDownToUp(this.heap);
}
/**
* 从小到大的堆
* @param heap
* @return
*/
private void createHeadDownToUp(List<Integer> heap){
//对数组进行堆排序
if(heap == null || heap.size() <= 0)
return;
int len = heap.size();
//从树的中间开始循环
for(int i = len / 2; i > 0; --i) {
//首先预存当前进行操作的节点‘
//索引和值
int selectIndex = i - 1;
int selectValue = heap.get(selectIndex);
boolean isHeap = false; //用来判断当前节点下是否已经没有其他节点比这个节点小了，作为是否成堆的标识
while(!isHeap && 2 * (selectIndex + 1) <= len) {
//当前节点的最大的孩子节点的位置，开始默认是第一个孩子节点的位置
int childIndex = 2 * i - 1;
//判断是否存在两个孩子节点，如果存在，那么就选出最大的那个
if(2 * i < len) {
//获取比较小的那个节点作为备选替换节点
childIndex = heap.get(childIndex) < heap.get(childIndex + 1) ? childIndex : childIndex + 1;
}
//判断当前节点是不是比下面最小的那个节点还要小
if(selectValue <= heap.get(childIndex)) {
//如果比下面最大的还大，那就表明这个节点为根的子树已经是一颗树了
isHeap = true;
} else {
//如果节点不是小的，那么更换掉
heap.set(selectIndex, heap.get(childIndex));
//并交换当前遍历交换的节点
selectIndex = childIndex;
//这个节点和子节点全部遍历结束之后，交换出最初用来交换的选中节点
heap.set(selectIndex, selectValue);
}
}
}
}
/**
* 对堆的节点的单次变换
* @param i 第几个节点
*/
private void shifHeadDownToUp(int i) {
if(heap == null || heap.size() <= 0)
return;
int len = this.heap.size();
//索引i需要存在于这个节点中
if(i >= len)
return;
// 首先预存当前进行操作的节点‘
// 索引和值
int selectIndex = i - 1;
int selectValue = heap.get(selectIndex);
boolean isHeap = false; // 用来判断当前节点下是否已经没有其他节点比这个节点小了，作为是否成堆的标识
while (!isHeap && 2 * (selectIndex + 1) <= len) {
// 当前节点的最大的孩子节点的位置，开始默认是第一个孩子节点的位置
int childIndex = 2 * (selectIndex + 1) - 1;
// 判断是否存在两个孩子节点，如果存在，那么就选出最大的那个
if (2 * (selectIndex + 1) < len) {
// 获取比较小的那个节点作为备选替换节点
childIndex = heap.get(childIndex) < heap.get(childIndex + 1) ? childIndex : childIndex + 1;
}
// 判断当前节点是不是比下面最小的那个节点还要小
if (selectValue <= heap.get(childIndex)) {
// 如果比下面最大的还大，那就表明这个节点为根的子树已经是一颗树了
isHeap = true;
} else {
// 如果节点不是小的，那么更换掉
heap.set(selectIndex, heap.get(childIndex));
// 并交换当前遍历交换的节点
selectIndex = childIndex;
// 这个节点和子节点全部遍历结束之后，交换出最初用来交换的选中节点
heap.set(selectIndex, selectValue);
}
}
}
//向堆添加元素
public void add(int element) {
// int oldLen = heap.size();
heap.add(element);
//然后从加入的位置的父节点开始，从下向上所有父节点，全部变换一次
for(int i = heap.size() / 2; i > 0; i = i / 2) {
this.shifHeadDownToUp(i);
}
}
/**
* 移除堆中一个指定元素
* @param index
* @return
*/
// public int remove(int index) {
// int result = heap.get(index - 1);
// //思路是吧剩下的最后一个元素作为参照元素，填充进去
// int lastValue = heap.get(heap.size() - 1);
// heap.set(index - 1, lastValue);
// heap.remove(heap.size() - 1);
// //然后从下向上，吧这个节点对应的位置的数据进行递归
// for(int i = index; i > 0; i = i / 2) {
// this.shifHeadDownToUp(i);
// }
// return result;
// }
public int remove(Integer object) {
int index = heap.indexOf(object);
//思路是吧剩下的最后一个元素作为参照元素，填充进去
int lastValue = heap.get(heap.size() - 1);
heap.set(index, lastValue);
heap.remove(heap.size() - 1);
//然后从下向上，吧这个节点对应的位置的数据进行递归
for(int i = index + 1; i > 0; i = i / 2) {
this.shifHeadDownToUp(i);
}
return index;
}
/**
* 默认删除根节点
* @return
*/
public int remove() {
int result = heap.get(0);
//思路是吧剩下的最后一个元素作为参照元素，填充进去
int lastValue = heap.get(heap.size() - 1);
heap.set(0, lastValue);
heap.remove(heap.size() - 1);
//然后从下向上，吧这个节点对应的位置的数据进行递归
for(int i = 1; i > 0; i = i / 2) {
this.shifHeadDownToUp(i);
}
return result;
}
@Override
public String toString() {
return heap.toString();
}
}