package 堆;
/**
*/
import java.util.Arrays;
public class TestHeap {
public int[] elem;
public int usedSize;
public TestHeap() {
this.elem = new int[10];
}
/**
* 向下调整
* 用于堆的创建性能更好，当然向上调整也是可以实现的
* parent：每次调整的根节点
* len：每次的结束位置
* 两孩子最大值和父比--》若大--》交换
若只有一个节点，不进入循环
*/
public void shiftDown(int parent,int len) {
int child = (2 * parent)+1;
//说明这棵树没有调整完
while (child < len) {
//如果有右孩子 你才去判断
if(child+1 < len && elem[child] < elem[child+1]) {
child++;
}
//child下标 一定是左右孩子最大值的下标
if(elem[child] > elem[parent]) {
int tmp = elem[parent];
elem[parent] = elem[child];
elem[child] = tmp;
parent = child;
child = 2*parent+1;
}else {
break;
}
}
}
/**
* 从后往前每一个都shiftdown
* 每一刻子树都是大堆那么总树就是一个大堆
* @param array
*/
public void createHeap(int[] array) {
this.elem = Arrays.copyOf(array,array.length);
// 和上边一样
// for (int i = 0; i < array.length; i++) {
// elem[i] = array[i];
// this.usedSize++;
// }
usedSize=array.length;
for (int i = (usedSize-1-1)/2; i >= 0 ; i--) {
shiftDown(i,usedSize);
}
}
/**
* 向上调整
* @param child
*/
public void shiftUp(int child) {
int parent = (child-1) / 2;
while (parent >= 0) {
if(elem[child] > elem[parent]) {
int tmp = elem[parent];
elem[parent] = elem[child];
elem[child] = tmp;
child = parent;
parent = (child-1)/2;
}else {
break;
}
}
}
/**
* 插入一个元素到堆中
* 先插到最后位置再向上调整
* @param val
*/
public void push(int val) {
if(isFull()) {
this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
}
this.elem[this.usedSize] = val;
this.usedSize++;
shiftUp(this.usedSize-1);
}
public boolean isFull() {
return this.usedSize == this.elem.length;
}
/**
* 出队，删除堆顶元素.
* 栈顶元素与最后元素交换
* usedsize--
* 向下调整
*/
public int pop() {
if(isEmpty()) {
return -1;
}
int tmp = elem[0];
elem[0] = elem[this.usedSize-1];
elem[this.usedSize-1] = tmp;
this.usedSize--;
shiftDown(0,this.usedSize);
return tmp;
}
public boolean isEmpty() {
return this.usedSize == 0;
}
/**
* 堆排序
*/
public void heapSort() {
int end = usedSize-1;
while (end > 0) {
int tmp = elem[end];
elem[end] = elem[0];
elem[0] = tmp;
shiftDown(0,end);
end--;
}
}
public void heapSort1() {
//createHeap();创建一个大根堆
int end = usedSize-1;
while (end > 0) {
int tmp = elem[end];
elem[end] = elem[0];
elem[0] = tmp;
shiftDown(0,end);
end--;
}
}
public static void main(String[] args) {
int[] array={ 27,15,19,18,28,34,65,49,25,37,99,88 };
TestHeap testHeap=new TestHeap();
testHeap.createHeap(array);
System.out.println(testHeap.pop());
System.out.println(testHeap.pop());
System.out.println(testHeap.pop());
System.out.println(testHeap.pop());
}
}