- inline int LEFT(int i)
- {
- return (i * 2 + 1);
- }
- inline int RIGHT(int i)
- {
- return (i * 2 + 2);
- }
- void swap(int &i, int &j)
- {
- int temp = i;
- i = j;
- j = temp;
- }
- void max_heapify(int a[], int n, int i)
- {
- int left = LEFT(i);
- int right = RIGHT(i);
- int max_idx = (left <n && a[i] < a[left]) ? left : i;
- max_idx = (right < n && a[max_idx] < a[right]) ? right : max_idx;
- if (i == max_idx) {
- return;
- }
- swap(a[i], a[max_idx]);
- max_heapify(a, n, max_idx);
- }
- void build_max_heap(int a[], int n)
- {
- for (int i = n / 2 - 1; i>= 0; i--) {
- max_heapify(a, n, i);
- }
- }
- void heap_sort(int a[], int n)
- {
- build_max_heap(a, n);
- for (int i = n - 1; i> 0; i--) {
- swap(a[i], a[0]);
- max_heapify(a, i, 0);
- }
- }
堆排序
来源: http://www.bubuko.com/infodetail-3282387.html