请选择 进入手机版 | 继续访问电脑版
搜索
房产
装修
汽车
婚嫁
健康
理财
旅游
美食
跳蚤
二手房
租房
招聘
二手车
教育
茶座
我要买房
买东西
装修家居
交友
职场
生活
网购
亲子
情感
龙城车友
找美食
谈婚论嫁
美女
兴趣
八卦
宠物
手机

数据结构篇——优先级队列(堆)

[复制链接]
查看: 57|回复: 0

7868

主题

1万

帖子

3万

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
31886
发表于 2019-11-9 09:05 | 显示全部楼层 |阅读模式
基天性质

优先级行列,也叫二叉堆、堆(不要和内存中的堆区搞混了,不是一个工具,一个是内存地域,一个是数据结构)。
堆的本质上是一种完全二叉树,分为:

  • 最小堆(小根堆):树中每个非叶子结点都不大于其左右孩子结点的值,也就是根节点最小的堆,图(a)。
  • 最大堆(大根堆):树中每个非叶子结点都不小于其左右孩子结点的值,也就是根节点最大的堆,图(b)。
数据结构篇——优先级队列(堆)  游戏 1470173-20191108185613754-1853469836
底子操纵

均以大根堆为例
存储方式

堆本质上是一颗完全二叉树,利用数组举行存储,从\(a[1]\)起头存储,这样对于下标为\(k\)的结点\(a[k]\)来说,其左孩子的下标为\(2*k\),右孩子的下标为\(2*k+1\)。,且不论 \(k\) 是奇数照旧偶数,其父亲结点(倘使有的话)就是 $\left \lfloor k/2 \right \rfloor $。
向上调解

假如我们向一个堆中插入一个元素,要使其仍然连结堆的结构。应当怎样办呢?
可以把想要增加的元素放在数组的末端,也就是完全二叉树的末端一个结点的后背,然后举行向上调解(heapinsert)。向上调解总是把欲调解结点与父亲结点比力,假如权值比父亲结点大,那末就交换其与父亲结点,频频比力,直到到达堆顶或父亲结点的值较大为止。向上调解暗示图以下:
数据结构篇——优先级队列(堆)  游戏 1470173-20191108195411666-343404772
代码以下,时候复杂度为\(O(logn)\):
  1. 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;    }}
复制代码
这样增加元素就很简单了
  1. void insert(int* arr, int n, int x) {    arr[++n] = x;//将x置于数组末端    heapinsert(arr, n);//向上调解x}
复制代码
向下调解

假如我们要删除一个堆中的堆顶元素,要使其仍然连结堆的结构。应当怎样办呢?
移除堆顶元素后,将末端一个元素移动到堆顶,然后对这个元素举行向下调解(heapify),向下调解总是把欲调解结点 \(K\) 与其左右孩子结点比力,假如孩子中存在权值比当前结点 \(K\) 大的,那末就将其中权值最大的那个孩子结点与结点 \(K\),频频比力,直到到结点 \(K\) 为叶子结点或结点 \(K\) 的值比孩子结点都大为止。向下调解暗示图以下:
数据结构篇——优先级队列(堆)  游戏 1470173-20191108195325641-1550788882
代码以下,时候复杂度也是\(O(logn)\):
  1. 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大元素
  1. 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(logn)\)
[code]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);    while (i < j) {        while (i < j && a[j] >= sign)j--;        while (i < j && a

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Copyright © 2006-2014 妈妈网-中国妈妈第一,是怀孕、育儿、健康等知识交流传播首选平台 版权所有 法律顾问:高律师 客服电话:0791-88289918
技术支持:迪恩网络科技公司  Powered by Discuz! X3.2
快速回复 返回顶部 返回列表