以下包含了最大堆,建堆以及堆排序
#include <iostream> using namespace std; void visitAllNode(int array[], int size) // 访问所有数据 { cout << array[0]; for (int i = 1; i < size; ++i) { cout << "-->" << array[i]; } cout << endl; } void max_heapify(int array[], int parent, int size) // 保持最大堆性质;最大堆:根节点永远大于左、右子节点 { int left = 2 * (parent + 1) - 1; // 左节点 int right = 2 * (parent + 1); // 右节点 int largest; // 寻找最大的节点位置 if (left < size && array[left] > array[parent]) largest = left; else largest = parent; if (right < size && array[right] > array[largest]) largest = right; if (largest != parent) // 最大值不是父节点 { swap(array[largest], array[parent]); // 交换成功 max_heapify(array, largest, size); // 需要保持最大堆性质 } } void build_max_heap(int array[], int size) // 建立最大堆 { for (int i = size/2; i > -1; --i) { max_heapify(array, i, size); // size/2是最大的父节点 } } void heap_sort(int array[], int size) // 堆排序 { build_max_heap(array, size); // 将数组建成最大堆 for (int i = size-1; i > 0; --i) { swap(array[0], array[i]); // 最大堆array[0]值最大,array[i]由后往前读取最大值 --size; // size减小,因为最后一个值已经排序完毕 max_heapify(array, 0, size); // array[0]已经和当前堆最后一个值进行交换,通过max_heapify()保持最大堆性质 } } int main() { int array[] = {5, 3, 7, 8, 4, 2, 1, 6, 9, 0}; int size = sizeof(array) / sizeof(array[0]); heap_sort(array, size); visitAllNode(array, size); system("pause"); return 0; }
在heap_sort函数中,传入max_heapify的参数size没有-1导致会错误的判断到已经排序好的数,这个应该注意!