- // 堆排序
- // Bery 2013-06-04
- // 参考资料:算法导论
- // 注意:
- // 使用数组表示,数组的第一个元素不存储有效元素,而是存储堆的有效元素个数
- #include <iostream>
- using namespace std;
- // 维护大根堆,数组中的第一个元素表示堆大小
- // arr:目标数组
- // i:要维护的子树的根下标
- void max_heapify(int arr[], int i)
- {
- int l = i * 2; // 左孩子
- int r = i * 2 + 1; // 右孩子
- int size = arr[0]; // 堆大小
- int largest = 0; // 最大值下标
- // 从根节点、左孩子和右孩子中找到最大值下标
- if (l <= size && arr[l] > arr[i])
- largest = l;
- else
- largest = i;
- if (r <= size && arr[r] > arr[largest])
- largest = r;
- // 交换
- if (largest != i)
- {
- int t = arr[i];
- arr[i] = arr[largest];
- arr[largest] = t;
- // 递归调用
- max_heapify(arr, largest);
- }
- }
- // 构造大根堆
- // arr:目标数组,数组中的第一个元素表示堆大小
- void build_max_heap(int arr[])
- {
- int size = arr[0];
- for (int i = size / 2; i > 0; i--)
- max_heapify(arr, i);
- }
- // 堆排序
- void heap_sort(int arr[])
- {
- int len = arr[0];
- for (int i = len; i > 1; i--)
- {
- // 交换
- int t = arr[1];
- arr[1] = arr[i];
- arr[i] = t;
- // 堆的有效元素个数减一,并维护堆
- arr[0]--;
- max_heapify(arr, 1);
- }
- }
- int main()
- {
- int arr[11] = { 10, 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 };
- build_max_heap(arr);
- // 期望输出:16 14 10 8 7 9 3 2 4 1
- cout << "大根堆\\n\\t";
- for (int i = 1; i < 11; i++)
- cout << arr[i] << '\\t';
- cout << endl;
- heap_sort(arr);
- cout << "排序后输出\\n\\t";
- for (int i = 1; i < 11; i++)
- cout << arr[i] << '\\t';
- cout << endl;
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/070320148896.html
来源: http://www.codesnippet.cn/detail/070320148896.html