堆实际上是一棵完全二叉树，其任何一个非叶节点满足：
arr[i]<=arr[2*i+1]&&arr[i]<=arr[2*i+2];(小顶堆)；
arr[i]<=arr[2*i+1]&&arr[i]<=arr[2*i+2];(大顶堆)；
下面是一个大顶堆的操作。
- 插入一个元素时
//插入一个元素时，将其插入堆的尾部，让后向上冒泡
public static void heapInsert(int[] arr,int index)
{
while (index!=0)
{
int parent=(index-1)/2;
if (arr[parent]<arr[index])
swap(arr,index,parent);
else
break;
index=parent;
}
}
- 堆化
//堆化，向下渗透
public static void heapify(int[] arr,int index,int size)
{
int left=2*index+1;
int right=2*index+2;
int best=index;
while (left<size)
{
if (arr[left]>arr[index])
{
best=left;
}
if (right<size&&arr[right]>arr[best])
{
best=right;
}
if (best!=index)
{
swap(arr,best,index);
}
else
break;
index=best;
left=2*index+1;
right=2*index+2;
}
}
- 删除堆中的最大值
//删除堆中的最大值
public static void deleteMax(int[] arr,int size)
{
//把最大值和数组尾部元素互换
swap(arr,0,size-1);
//数组尾部元素设为-1
arr[--size]=-1;
//堆化
heapify(arr,0,size);
}
