数据结构 |
您所在的位置：网站首页 › 队列叫什么 › 数据结构 |
数据结构
|
基本性质
优先级队列，也叫二叉堆、堆（不要和内存中的堆区搞混了，不是一个东西，一个是进程的内存区域，一个是数据结构）。 堆的本质上是一种完全二叉树，分为： 最小堆（小根堆）：树中每个非叶子结点都不大于其左右孩子结点的值，也就是根节点最小的堆，图（a）。 最大堆（大根堆）：树中每个非叶子结点都不小于其左右孩子结点的值，也就是根节点最大的堆，图（b）。
以下操作均以大根堆为例 存储方式 堆本质上是一颗完全二叉树，使用数组进行存储，从 a [ 0 ] a[0] a[0] 还是 a [ 1 ] a[1] a[1] 开始存储，对于索引为 k k k 的结点，其左孩子、右孩子和父节点索引情况如下： 第一个存储位置左孩子右孩子父节点 a [ 1 ] a[1] a[1] 2 ∗ k 2*k 2∗k 2 ∗ k + 1 2*k+1 2∗k+1$\left \lfloor k/2 \right \rfloor $ a [ 0 ] a[0] a[0] 2 ∗ k + 1 2*k+1 2∗k+1 2 ∗ ( k + 1 ) 2*(k+1) 2∗(k+1)$\left \lfloor (k-1)/2 \right \rfloor $ 向上调整假如我们向一个堆中插入一个元素，要使其仍然保持堆的结构。在数组的最后添加一个元素，作为堆的一个叶子结点，然后对这个元素进行向上调整； 向上调整总是把欲调整结点与父亲结点比较，如果权值比父亲结点大，那么就交换其与父亲结点，反复比较，直到到达堆顶或父亲结点的值较大为止。向上调整示意图如下： 
代码如下，时间复杂度为 O ( l o g n ) O(logn) O(logn)： void heapinsert(int* arr, int n) { int k = n; //如果 K 结点有父节点，且比父节点的权值大 while (k > 1 && arr[k] > arr[k / 2]) { //交换 K 与父节点的值 swap(arr[k / 2], arr[k]); k >>= 1; } }这样添加元素就很简单了 void insert(int* arr, int n, int x) { arr[++n] = x;//将x置于数组末尾 heapinsert(arr, n);//向上调整x } 向下调整假如我们要删除一个堆中的堆顶元素，要使其仍然保持堆的结构。删除数组的第一个元素，把将最后一个元素移动到堆顶，然后对这个元素进行向下调整 向下调整总是把欲调整结点 K K K 与其左右孩子结点比较，如果孩子中存在权值比当前结点 K K K 大的，那么就将其中权值最大的那个孩子结点与结点 K K K，反复比较，直到到结点 K K K 为叶子结点或结点 K K K 的值比孩子结点都大为止。向下调整示意图如下： 
代码如下，时间复杂度也是 O ( l o g n ) O(logn) O(logn)： void heapify(int* arr, int k, int n) { //如果结点 K 存在左孩子 while (k * 2 = 1; i--) { heapify(arr, i, n); } for (int i = 50; i > 1; i--) { swap(arr[1], arr[i]); heapify(arr, 1, i - 1); } } 寻找第K大元素首先用数组的前k个元素构建一个小根堆，然后遍历剩余数组和堆顶比较，如果当前元素大于堆顶，则把当前元素放在堆顶位置，并调整堆（heapify）。遍历结束后，堆顶就是数组的最大k个元素中的最小值，也就是第k大元素。 void heapify(int* a, int index, int length) { int left = index * 2 + 1; while (left a[left])break; swap(a[index], a[left]); index = left; } } void ArrayToBheap(int* a, int length) { int i = length / 2 - 1; for (; i >= 0; i--) { heapify(a, i, length); } } void FindKMax(int* a, int k, int length) { ArrayToBheap(a, k); for (int i = k; i < length; i++) { if (a[i] > a[0]) a[0] = a[i]; heapify(a, 0, k); } }时间复杂度 O ( n ) O(n) O(n)，只是举个例子。 事实上对于这个问题是有更快的做法的，快速排序的思想，时间复杂度 O ( l o g n ) O(logn) O(logn) int Search_K(int left, int right, int k) { int i = left, j = right; int p = rand() % (right - left + 1) + left; int sign = a[p]; swap(a[p], a[i]); while (i < j) { while (i < j && a[j] >= sign)j--; while (i < j && a[i] q1.push(rand() % 100); q2.push(rand() % 100); } while (!q1.empty()) { printf("%d ", q1.top()); q1.pop(); } printf("\n"); while (!q2.empty()) { printf("%d ", q2.top()); q2.pop(); } return 0; }对于自定义类型，可以重载operator} //返回true时，说明this的优先级低于b bool operator // return a.x > b.x;//a.x大，反而优先级低，所以这是个小跟堆 //} int main() { priority_queue q; for (int i = 0; i int x; Node(int a) :x(a) {} }; struct cmp { bool operator() (Node a, Node b) {//默认是less函数，返回true时，左边的优先级低于右边的优先级 return a.x > b.x; //同样这是个小跟堆 } }; int main() { priority_queue q; for (int i = 0; i _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Ty _FIRST_ARGUMENT_TYPE_NAME; _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Ty _SECOND_ARGUMENT_TYPE_NAME; _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef bool _RESULT_TYPE_NAME; constexpr bool operator()(const _Ty& _Left, const _Ty& _Right) const { return _Left // push *(_Last - 1) onto heap at [_First, _Last - 1), using _Pred _Adl_verify_range(_First, _Last); const auto _UFirst = _Get_unwrapped(_First); auto _ULast = _Get_unwrapped(_Last); using _Diff = _Iter_diff_t; _Diff _Count = _ULast - _UFirst; if (2 // percolate _Hole to _Top or where _Val belongs, using _Pred using _Diff = _Iter_diff_t; for (_Diff _Idx = (_Hole - 1) >> 1; // shift for codegen _Top > 1) { // shift for codegen // move _Hole up to parent *(_First + _Hole) = _STD move(*(_First + _Idx)); _Hole = _Idx; } *(_First + _Hole) = _STD move(_Val); // drop _Val into final hole } 关键是这一句， _DEBUG_LT_PRED(_Pred, *(_First + _Idx), _Val)，传入的仿函数用在了这里，当 *(_First + _Idx) < _Val 时返回 true ，即当父节点的值小于新插入的值时继续调整，less函数返回true，父节点被插入结点换了下去，所以我们才可以得出上面用的结论 less函数，返回true时，左边的优先级低于右边的优先级，也就清楚了为什么默认传入less反而形成的是大根堆。 |
【本文地址】
今日新闻 |
推荐新闻 |