本文内容来源于《漫画算法》和数据结构教材
这里提到的堆是一个二叉堆，本质上是一颗完全二叉树。堆排序只需要一个记录大小的辅助空间。
1.java实现
/**
* 下沉调整
* @param arr 待调整的堆
* @param parentIndex 要下沉的父节点下标
* @param length 堆的有效大小(一般指存储堆的数组长度)
*/
void downAdjust(int[] arr, int parentIndex, int length) {
// temp保存父节点的值，用于最后的赋值
int temp = arr[parentIndex];
int childIndex = 2 * parentIndex + 1;
while (childIndex < length) {
// 如果有rightChild，并且rightChild值大于leftChild值，则childIndex指向rightChild
if (childIndex + 1 < length && arr[childIndex + 1] > arr[childIndex]) {
childIndex++;
}
// 如果父节点大于子节点中的最大元素，则跳出循环，因为无需下沉
if (temp >= arr[childIndex])
break;
//
arr[parentIndex] = arr[childIndex];
parentIndex = childIndex;
childIndex = 2 * childIndex + 1;
}
arr[parentIndex] = temp;
}
/**
* 堆排序(升序)
* @param arr 待调整的堆
*/
void heapSort(int[] arr) {
// 1.把无序数组构建成最大堆[从最后一个非叶子节点，逐个向前进行下沉调整]
for (int i = (arr.length - 2) / 2; i >= 0; i--) {
downAdjust(arr, i, arr.length);
}
System.out.println(Arrays.toString(arr));
// 2.循环删除(并非真正意义的删除，只是移动到最后)堆顶元素，移到集合尾部，调整堆产生新的堆顶
for (int i = arr.length - 1; i > 0; i--) {
// 最后一个元素和第一个元素进行交换
int temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;
// 下沉调整
downAdjust(arr, 0, i);
}
}
@Test
public void fun1() {
int[] arr = new int[] { 1, 3, 2, 6, 5, 7, 8, 9, 10, 0 };
heapSort(arr);
System.out.println(Arrays.toString(arr));
}
2.C语言实现
/*
* 堆排序的实现
* 数据结构(C语言版本) 严蔚敏 吴伟民
*
实现堆排序需要解决2个问题：
(1)如何由一个无序序列建成一个堆？
(2)如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？
*/
#include<iostream>
using namespace std;
/*
堆的调整
s 根节点索引
m 数组有效长度
调整为大顶堆
*/
void HeapAdjust(int arr[], int s, int m) {
//cout<<"m"<<m<<endl;
// 保存需要调整的节点
int temp = arr[s];
for (int j = 2 * s + 1; j <= m; j = 2 * j + 1) { // 沿key较大的孩子节点向下筛选
/*
cout<<"parent "<<arr[s]<<endl;
cout<<"left "<<arr[j]<<endl;
if(j+1<=m)
cout<<"right "<<arr[j+1]<<endl;
else
cout<<"right"<<" is empty"<<endl;
cout<<"+"<<j<<endl;
*/
if (j < m && arr[j] < arr[j + 1]) // j为key较大的记录的下标
++j;
//cout<<"="<<j<<endl;
if (temp > arr[j]) {
//cout<<temp<<"gt"<<arr[j]<<" end for loop"<<endl;
break;
}
arr[s] = arr[j]; // 较大的节点"上浮"
/*
这里省略了arr[j]=temp;这一步多余了，
只需要在最后执行这一步，将最初的s指向的元素放到最终位置即可
*/
arr[j] = temp; //(1)可以在调试的时候加上这句话，方便查看最终结果
s = j; // 父节点索引指向刚调整的j位置
}
arr[s] = temp; //如果循环没有发生数据交换，这一步就没必要啦，有也不会错。
//cout<<"**********************"<<endl;
}
void HeapSort(int arr[]) {
// 1.构建堆(这个堆是一个二叉堆，本质是一颗完全二叉树)
int len = 8;
for (int i = len / 2 - 1; i >= 0; --i) {
HeapAdjust(arr, i, len - 1);
}
cout << "-------------------------" << endl;
// 2.调整剩余元素成为一个新的堆
for (int i = len - 1; i > 0; --i) {
// 堆顶元素和当前未经排序子序列arr[0..i]中最后一个记录相互交换
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
HeapAdjust(arr, 0, i - 1); // 将arr[0..i-1]重新调整为大顶堆
}
}
int main(int argc, char* argv[]) {
int arr[] = { 49, 38, 65, 97, 76, 13, 27, 49 };
HeapSort(arr);
int len = 8;
for (int i = 0; i < len; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
堆排序的练习java版[漫画算法]
堆本质上是一颗完全二叉树，用数组存储，
parent,leftChild,rightChild
他们之间的数组下标的关系如下：
{
l
e
f
t
C
h
i
l
d
=
2
∗
p
a
r
e
n
t
+
1
;
r
i
g
h
t
C
h
i
l
d
=
2
∗
p
a
r
e
n
t
+
2
;
\begin{cases}leftChild=2*parent+1;\\ rightChild=2*parent+2;\end{cases}
{leftChild=2∗parent+1;rightChild=2∗parent+2;
堆排序算法步骤
1.把无序数组构建成二叉堆。
2.循环删除堆顶元素，并将该元素移到集合尾部，调整堆产生新的堆顶。
(这里的删除并非真的删除只是移动到了数组的后面相应的位置上)
时间复杂度O(nlogn)
空间复杂度O(1)
从宏观上看堆排序和快速排序的异同
相同点，1.堆排序和快速排序的平均时间复杂度都是O(nlogn)，并且都是不稳定排序。
不同点，1.快速排序的最坏时间复杂度是O(n^2)；而堆排序的最坏时间复杂度稳定在O(nlogn)
2.此外快排的递归和非递归方式的空间复杂度都是O(logn)，
而堆排序的空间复杂度是O(1)
在漫画算法里面，有许多的堆调整的示意图，非常有助于理解。
堆的定义如下：n个元素的序列
{
k
1
,
k
2
,
.
.
.
,
k
n
,
}
\lbrace k_{1},k_{2},...,k_{n}, \rbrace
{k1,k2,...,kn,}当且仅当满足如下关系时，称之为堆。这里教材定义的下标是从1开始的，实际程序的下标是从0开始的，注意转换
{
k
i
⩽
k
2
i
k
i
⩽
k
2
i
+
1
\begin{cases} k_{i} \leqslant k_{2i}\\ k_{i} \leqslant k_{2i+1} \end{cases}
{ki⩽k2iki⩽k2i+1或
{
k
i
⩾
k
2
i
k
i
⩾
k
2
i
+
1
\begin{cases} k_{i} \geqslant k_{2i}\\ k_{i} \geqslant k_{2i+1} \end{cases}
{ki⩾k2iki⩾k2i+1
(
i
=
1
,
2
,
.
.
.
,
⌊
n
2
⌋
)
(i=1,2,...,\lfloor \frac{n}{2} \rfloor)
(i=1,2,...,⌊2n⌋)
若将和此序列对应的一维数组（即以一维数组做此序列的存储结构）看成是一个完全二叉树，则堆的含义表名，完全二叉树中所有非终端节点的值均不大于（或不小于）其左右孩子节点的值。由此，若序列
{
k
1
,
k
2
,
.
.
.
,
k
n
,
}
\lbrace k_{1},k_{2},...,k_{n}, \rbrace
{k1,k2,...,kn,}是堆，则堆顶元素（或完全二叉树的根）必为序列中n个元素的最小值（或最大值）。
漫画算法里面的定义还是比较浅显易懂的。教材定义太复杂和吓人。
