数据结构中的堆是一颗完全二叉树，一般由数组实现（也有优先队列），这篇主要讲一下用数组实现的堆。
1： 对一个普通数组进行堆排序（尤其是原地排序，不能占用额外空间的）其实这样的堆排序我很难说他实现了堆，它只是对普通数组使用了堆的特性 （并没有堆的数据结构的实现）
这种一般要经过两个步骤：
1 建堆 把整个初始数组进行变化成一个符合大顶堆（小顶堆）的数组，一般来说升序用大顶堆降序用小顶堆。
下面是一个简单的实现 直接调用sort就行
public static void sort(int[] arr) {
//建大顶堆 对所有的非叶子节点 对每一个节点进行adjustHeap
for (int i = arr.length / 2 - 1; i >= 0; i--) {
adjustHeap(arr, i, arr.length);
}
/**
* 调整堆得过程是这样的 我们建立大顶堆 保证了堆顶是目前最大的元素
* 然后将堆顶和堆最后一个值交换 这样最后一个值已经是最大值，那么我们在调整堆得时候就可以忽略这个值
* 同理数组第二大的值会被放到堆的倒数第二个位置 。。。。
* 每一次调整之后 只有堆顶元素需要调整 所以执行一次 adjustHeap()
* 这样就可以完成排序
*/
for (int i = arr.length - 1; i > 0; i--) {
swap(arr, 0, i);
adjustHeap(arr, 0, i);
}
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
/**
* 这个函数的目的是将数组节点i进行调整
* 调整过程其实是这样的
* 假设堆顶元素是 1 要调整经过的路径是 1(堆顶元素) 11 8 6 0
* 第一次i = 0比较后变为 11(因为执行了这一句 arr[i] = arr[largeChild]) 11 8 6 0
* 第二次i = 2 比较后变为 11 8 8 6 0
* 。。。
* 最后一次比较 1>0 循环结束 将 11 8 6 6 0 变为 11 8 6 1 0
* 调整结束(temp一直表示的是堆顶元素的值)
* @param arr
* @param i
* @param length
*/
public static void adjustHeap(int[] arr, int i, int length) {
int largeChild;
int temp = arr[i];
// length/2是第一个叶子节点的下标 所以判断范围是小于这个值
while (i < length / 2) {
//左孩子节点
int left = i * 2 + 1;
//右孩子节点
int right = left + 1;
//因为要构建大顶堆 所以要和左右节点中较大的值（如果有）交换
if (right < length && arr[left] < arr[right]) {
largeChild = right;
} else {
largeChild = left;
}
//如果当前值小于堆顶值 结束循环（找到了要插入的位置）
if (temp >= arr[largeChild]) {
break;
}
arr[i] = arr[largeChild];
i = largeChild;
}
arr[i] = temp;
}
而我们要实现一种堆的数据结构，最基本的这个堆至少有添加数据和删除数据的功能。下面我以n个排序数组合并为例实现一下堆的数据结构
class Node {
private int value;
private int index;
public Node(int value, int index) {
this.value = value;
this.index = index;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public int getIndex() {
return index;
}
public void setIndex(int index) {
this.index = index;
}
}
private Node[] nodes;
//堆当前元素数量
private int curSize;
public Heap(int maxSize) {
//初始化堆
this.nodes = new Node[maxSize];
this.curSize = 0;
}
public int getCurSize() {
return curSize;
}
public Node[] getNodes() {
return nodes;
}
public boolean isEmpty() {
return this.curSize == 0;
}
public void insert(Node node) {
nodes[curSize] = node;
up(curSize++);
}
public void remove() {
nodes[0] = nodes[--curSize];
down(0);
}
/**
* 这个函数的功能是将nodes[index]为根的二叉树构建为小顶堆
* 其实有点像插入排序(将一个数插入一个有序数组中)
*
* @param index
*/
public void down(int index) {
int largeChild;
Node top = nodes[index];
//不用判断叶子节点
while (index < (curSize) / 2) {
int left = 2 * index + 1;
int right = 2 * index + 2;
//找出左右孩子节点中较小的那一个 显然如果没有右节点为左节点
if (right < curSize && nodes[left].getValue() >= nodes[right].getValue()) {
largeChild = right;
} else {
largeChild = left;
}
//如果top值小于孩子节点 直接结束循环(可以理解为找到了插入的位置)
if (top.getValue() <= nodes[largeChild].getValue()) {
break;
}
nodes[index] = nodes[largeChild];
index = largeChild;
}
nodes[index] = top;
}
public void up(int index) {
int parent = (index - 1) / 2;
Node temp = nodes[index];
while (index > 0 && nodes[parent].getValue() >= temp.getValue()) {
nodes[index] = nodes[parent];
index = parent;
parent = (parent - 1) / 2;
}
nodes[index] = temp;
}