郑州建站优化,高新区网站建设 意义,网站开发需求清单,网站如何动态修改主页在讨论「堆排序」之前#xff0c;先复习一下「选择排序」。 void SelectionSort(int a[], size_t n) {for (size_t i 0; i n; i) {// 在剩余元素中找出最小的一个#xff0c;然后与 a[i] 交换。size_t k i;for (size_t j i1; j n; j) {if (a[j] a[k]) {k … 在讨论「堆排序」之前先复习一下「选择排序」。 void SelectionSort(int a[], size_t n) {for (size_t i 0; i n; i) {// 在剩余元素中找出最小的一个然后与 a[i] 交换。size_t k i;for (size_t j i1; j n; j) {if (a[j] a[k]) {k j;}}if (k ! i) {std::swap(a[i], a[k]);}}
} 选择排序的空间效率很高O(1)但是时间效率很低O(N^2)主要花在了「从剩余元素中找出最小元素」每次都要遍历剩余的全部元素。 有没有一种数据结构能够方便的拿到 最小 元素 如果重写 SelectionSort改为反向遍历每次「从剩余元素中找出最大元素」 void SelectionSort(int a[], size_t n) {for (size_t i n-1; i 0; --i) {// 在剩余元素中找出最大的一个然后与 a[i] 交换。size_t k i;for (size_t j 0; j i; j) {if (a[j] a[k]) {k j;}}if (k ! i) {std::swap(a[i], a[k]);}}
} 那么问题就可以改成有没有一种数据结构能够方便的拿到 最大 元素 堆就是这样一种数据结构。 其实堆有「最大堆」和「最小堆」之分但是差别不大这里以最大堆为例是为了便于实现堆排序这也是改写 SelectionSort 的原因。 堆是一种在数组上实现的几乎完全的二叉树子节点小于父节点所以根节点总是最大。 记 H[1..n] 为堆以 H[i] 表示数组中第 i 个元素它的父节点位于 i/2子节点分别位于 i*2 和 i*21。 这种通过数组下标的关系来连接父子节点的方式比一般的树型节点省了两个指针的空间。 给定一个堆 [ 30, 26, 13, 17, 11, 7, 8, 10, 4, 3 ]那么对应的树型结构为 30/ \26 13/ \ / \17 11 7 8/ \ /10 4 3 假如有一个数组 [ 4, 3, 7, 10, 11, 13, 8, 26, 17, 30 ]怎么把它转换成堆呢 4/ \3 7/ \ / \10 11 13 8/ \ /26 17 30 从最小最靠近叶节点的子树开始如果根节点比子节点小就与之交换依次按如下步骤进行调整。 第一步 11* 30/ -- /30 11* 第二步 10* 26/ \ -- / \26 17 10* 17 第三步 7* 13/ \ -- / \13 8 7* 8 第四步 3*/ \26 30/ \ /10 17 11--30/ \26 3*/ \ /10 17 11--30/ \26 11/ \ /10 17 3* 第五步 4*/ \30 13/ \ / \26 11 7 8/ \ /10 17 3--30/ \4* 13/ \ / \26 11 7 8/ \ /10 17 3--30/ \26 13/ \ / \4* 11 7 8/ \ /10 17 3--30/ \26 13/ \ / \17 11 7 8/ \ /10 4* 3 经过这五步堆就建好了。下面以 C 代码示范。 MakeHeap 把一个数组转换成堆 void MakeHeap(A a) {for (size_t i a.size() / 2; i 0; --i) {SiftDown(a, a.size(), i);}
} 类型 A 就是 std::vector。当然用 C 数组也可以只是后续讨论插入操作时会比较麻烦。 typedef std::vectorint A; MakeHeap 通过 SiftDown 把每棵子树的根节点向下调整。 // SiftDown 把堆 h[1..n] 的第 i 个元素向下调整i 从 1 打头。
void SiftDown(A h, size_t n, size_t i) {while (true) {i i * 2;if (i n) {break;}if (i n h[i] h[i-1]) {i;}if (h[i-1] h[i/2-1]) {std::swap(h[i-1], h[i/2-1]);} else {break;}}
} MakeHeap 的用法 int data[10] { 4, 30, 8, 17, 26, 13, 7, 3, 10, 11 };
A a(data, data 10);
MakeHeap(a); 堆排序 void HeapSort(A a) {MakeHeap(a); // 首先把数组 a 转换成堆。// 反向遍历每次把堆的根与第 i 个元素交换。// 每次交换后用 SiftDown 把新的根向下调整。for (size_t i a.size(); i 1; --i) {std::swap(a[0], a[i-1]);SiftDown(a, i-1, 1);}
} 堆排序与选择排序极为相似空间效率一样时间效率更优O(N*logN)。 与 SiftDown 相反的操作为 SiftUp。 // SiftUp 把堆 h[1..n] 的第 i 个元素向上调整i 从 1 打头。
void SiftUp(A h, size_t i) {while (i 1) {if (h[i-1] h[i/2-1]) {std::swap(h[i-1], h[i/2-1]);}i i / 2;}
} 插入操作依赖于 SiftUp先添加到数组末尾然后通过 SiftUp 把新元素向上调整。 void Insert(A h, int x) {h.push_back(x);SiftUp(h, h.size());
} 删除操作依赖于 SiftDown先把要删除的第 i 个元素与最后一个元素交换然后收缩数组再通过 SiftDown 把交换上来的元素向下调整。 void Delete(A h, size_t i) {size_t n h.size();if (n 0 || i 0 || i n) {return;}if (i n) {h.resize(n - 1);return;}std::swap(h[i - 1], h[n - 1]);h.resize(n - 1);SiftDown(h, n - 1, i);
}
