前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >每日一题:堆排序中建堆过程的时间复杂度是

每日一题:堆排序中建堆过程的时间复杂度是

作者头像
程序员小王
发布2021-06-25 20:14:09
7710
发布2021-06-25 20:14:09
举报
文章被收录于专栏:架构说

end


来源:https://www.nowcoder.com/questionTerminal/385157a6b64540c3b233bd12f8a83ee7

其实,建堆的整个过程中一个节点的比较次数是与它的高度k成正比的,比如,上图中的1这个元素,它也是从最后一层依次比较了3次(高度h=4),才到达了现在的位置。

所以,我们可以得出第h层的元素有1个,它最多需要比较(h-1)次;第(h-1)层有2个元素,它们最多比较(h-2)次;第(h-2)层有22个元素,它们最多比较(h-3)次;...;第1层有2(h-1)个元素,它们最多比较0次。

构造二叉堆的时间复杂度为线性

构造二叉堆的时间复杂度为线性

构造二叉堆的时间复杂度为线性

heap property

关系:元素之间的关系

What are the minimum and maximum numbers of elements in a heap of height h?

The BUILD-MAX-HEAP procedure, which runs in linear time, produces a max- heap from an unordered input array.

The BUILD-MAX-HEAP procedure, which runs in linear time, produces a max- heap from an unordered input array.

The procedure BUILD-MAX-HEAP goes through the remaining nodes of the tree and runs MAX-HEAPIFY on each one.

BUILD-MAX-HEAP.A/

  1. 1 A:heap-size D A:length
  2. 2 for i D bA:length=2c downto 1

3 MAX-HEAPIFY.A;i/

Exercises

6.2-1

Using Figure 6.2 as a model, illustrate the operation of MAX-HEAPIFY.A;3/ on the array A D h27;17;3;16;13;10;1;5;7;12;4;8;9;0i.

6.2-2

Starting with the procedure MAX-HEAPIFY, write pseudocode for the procedure MIN-HEAPIFY.A;i/, which performs the corresponding manipulation on a min- heap. How does the running time of MIN-HEAPIFY compare to that of MAX- HEAPIFY?

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2021-06-03,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 Offer多多 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档