当前位置: 首页 > news >正文

惠州网站制作推广公司排名百度商务合作联系

惠州网站制作推广公司排名,百度商务合作联系,深圳网站设计哪家公司好,广告店需要学什么技术优先队列 API初级实现使用堆实现由下至上的堆有序化(上浮)由上至下的堆有序化(下沉)插入和删除元素具体实现 很多情况下我们需要有序的处理输入的元素,但是又不需要输入的元素全部有序,或者不需要一次将它们…

优先队列

      • API
      • 初级实现
      • 使用堆实现
        • 由下至上的堆有序化(上浮)
        • 由上至下的堆有序化(下沉)
        • 插入和删除元素
        • 具体实现

很多情况下我们需要有序的处理输入的元素,但是又不需要输入的元素全部有序,或者不需要一次将它们排序出来。还有的情况的输入的元素不是一次性给出的,需要我们根据需要实时获取最大值或者最小值。这时候我们就可以使用优先队列实现我饿们的需求。

API

public class MaxPQ <Key extends Comparable<Key>>
MaxPQ()创建一个优先队列
MaxPQ(int max)创建一个初始容量为max的优先队列
MaxPQ(Key[] a)用a[]中的元素创建一个优先队列
void insert(Key v)向优先队列中插入一个元素
Key max()返回最大元素
Key delMax()删除返回最大元素
boolean isEmpty()返回队列是否为空
int size()返回优先队列中元素个数

初级实现

初级实现是使用一个数组或者链表,在插入时或者获取最大元素动态维护数组或者链表的有序性并使得调用对应获取最大值的API能正确获取结果。

使用堆实现

当一棵二叉树的每个结点都大于等于它的两个子节点时,它被称为堆有序。根节点是堆有序的二叉树中的最大结点。二叉堆是一组能够用堆有序的完全二叉树排序的元素,并在数组中按照层级存储(不使用数组的第一个位置)

由下至上的堆有序化(上浮)

如果堆有序的状态因为某个节点变得比它的父节点更大而被打破,那么我们就需要通过交换它和它的父节点来修复堆。交换后,这个节点比它的两个子节点都打,但这个节点仍然可能比它现在的父节点更大。我们可以一遍遍地使用同样地办法恢复秩序,将这个节点不断向上移动直到我们遇到一个更大的父节点。

private void swim(int k) {while (k > 1 && less(k / 2, k)) {exch(k/2, k);k /= 2;}
}

由上至下的堆有序化(下沉)

如果堆有序状态因为某个结点变得比它的两个子节点或是其中之一更小而被打破了,那么我们可以通过将它和它的两个子节点中的较大者交换来恢复堆。交换可能会在子节点处继续打破堆的有序状态,因此我们需要不断地用相同的方式将其修复,将节点下移直到它的子节点都比它更小或者到达了堆的底部。

private void sink(int k) {while (2 * k <= N) {int j = 2 * k;if (j < n && less(j, j + 1)) ++j;if (!less(k, j)) break;exch(k, j);k = j;}
}

插入和删除元素

插入新元素:我们将新元素添加到数组末尾,增加堆的大小并让这个新元素上浮到合适的位置。
删除最大元素:我们将数组顶端删去最大的元素并将数组的最后一个元素放到顶端,减小堆的大小并让这个元素下沉到合适的位置。

具体实现

public class MaxPQ <Key extends Comparable<Key>> {private Key[] pq;private int N = 0;public MaxPQ(int maxN) {pq = (Key[]) new Comparable[maxN + 1];}public boolean isEmpty() {return N == 0;}public int size() {return N;}public void insert(Key v) {pq[++N] = v;swim(N);}public Key delMax() {Key max = pq[1];exch(1, N--);pq[N + 1] = null;sink(1);return max;}private boolean less(int i, int j)private void exch(int i, int j)private void swim(int k)private void sink(int k)
}

对于一个含有N个元素的基于堆的优先队列,插入元素操作只需不超过(logN + 1)次比较,删除最大元素的操作需要不超过2logN次比较

http://www.rdtb.cn/news/20818.html

相关文章:

  • 大理建设学校官方网站合肥seo排名收费
  • 外语网站建设推广普通话手抄报
  • 天津企业网站建设价格seo产品优化推广
  • 请问做网站需要什么中国企业网络营销现状
  • 智慧团建注册登录入口下载seo具体是什么
  • 建设网站群的意义营销排名seo
  • 淮南网站建设好nba赛季排名
  • 嘉兴网站推广优化费用今日国家新闻
  • zhongwen网站模板爱站工具包下载
  • php java做网站郑州网站关键词优化外包
  • 微信用网站怎么做店铺如何运营和推广
  • 政府网站建设先进个人先进事迹网络seo软件
  • 网站开发的目的网络推广靠谱吗
  • 做日本淘宝网站江西seo推广
  • 什么网站用来做商城好温州seo优化
  • 某种网站怎么找网站推广平台有哪些
  • 怎么做一个网站怎么样常见搜索引擎有哪些
  • wordpress 8个安全密匙百度地图排名可以优化吗
  • 南京哪里有做公司网站的市场调研报告模板ppt
  • 只做特卖的网站志鸿优化设计电子版
  • 网站建设优势百度指数查询排行榜
  • 用代码怎么做网站国内搜索引擎排名2022
  • 网站制作及维护合同网站目录
  • 代理公司注册济南盐城seo营销
  • 网站基础建设巴巴商友圈广州网站优化公司排名
  • 东莞黄江做网站公司海南seo
  • 免费做微信请帖的网站seo人才网
  • 英语不好的做网站运营可以吗免费推广网站有哪些
  • 开发一个网站需要几个人口碑营销的产品有哪些
  • 网站网站建设专业考研培训机构排名前十