p; }
}
heapArray[index] = top;
}
/**
* 测试堆的使用是否正常
*/
public static void main(String[] args) {
Heap heap = new Heap(10);
Random random = new Random();
//逐个节点进行插入
for (int i = 0; i < 10; i++) {
heap.insert(random.nextInt(100));
}
for (int i = 0; i < 10; i++) {
System.out.print(heap.heapArray[i].getKey()+" ");
}
System.out.println("这是逐个节点插入后的结果");
//对数组进行操作，使其成为堆
for (int i = 0; i < 10; i++) {
Node node =new Node(random.nextInt(100));
heap.heapArray[i] = node;
}
//对数组进行调整
for (int i = heap.currentSize/2-1; i >= 0; i--) {
heap.trickleDown(i);
}
for (int i = 0; i < 10; i++) {
System.out.print(heap.heapArray[i].getKey()+" ");
}
System.out.println("这是调整后的结果");
//堆的移除操作
for (int i = 0; i < 10; i++) {
System.out.print(heap.remove().getKey()+" ");
}
}
static class Node{
int key;
public Node(int key){
this.key = key;
}
int getKey(){
return key;
}
}
}
六、堆排序
堆排序(Heapsort)是利用堆所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。就大根堆而言，我们已经知道大根堆的要求是每个节点的值都不大于其父节点的值。在数组的非降序排序中，需要使用的就是大根堆，因为大根堆的最大的值一定在堆顶。
堆排序是利用删除堆的根节点和调整堆的过程实现的。首先是根据所要进行排序的数组元素构建堆。然后将堆的根节点（根节点为最大值）取出(一般是与最后一个节点进行交换)，将前面len-1个节点继续进行堆调整的过程，然后再将根节点取出，这样一直到所有节点都取出。堆排序过程的时间复杂度是O(nlgn)。因为建堆的时间复杂度是O(n)（调用一次）；调整堆的时间复杂度是lgn，调用了n-1次，所以堆排序的时间复杂度是O(nlgn)。
七、堆排序实现
第一步，将要排序的数组建成大顶堆。
第二步，将此大顶堆的根元素与最后一个元素交换，这样就把最大值放到数组最后一个位置去了，并且将新换的元素进行向下筛选，筛选完成后又恢复了堆结构。接着将根节点与倒数第二个节点交换，再重复上述步骤，这样就形成了在这个数组的前部分为无序区，后部分为有序区，一直将第一个元素（根节点）与无序区的最后一个元素进行交换，知道无序区的长度为2时截止，这时我们也就将整个数组进行排序完毕了。
Java代码实现：
public static int [] heapSort(int []s){
//第一步，建立大顶堆