专栏首页架构说每日一题:堆排序中建堆过程的时间复杂度是

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

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?

本文分享自微信公众号 - 架构说(JiaGouS),作者:王传义

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-06-03

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 吃土记:之前理解时间复杂度计算方式是错误的

    程序员小王
  • Day29:最小的K个数

    思路   我们看题意可知,今天的题目和上一道题比较的类似,上一道题是将数组中重复数字次数超过数组长度一半输出来这个数字。而今天的的数字是输出最小K个数。都是要...

    一计之长
  • TopN问题

    建一个K个数的最小堆,与堆顶比较,大于(等于)堆顶,依次插入堆,超过K个数,踢出堆顶

    搬砖俱乐部
  • 堆排序

    面试官:写一个堆排吧 我心想:幸好昨天刚看 ? 堆排是基于堆的一种排序算法,对于堆的了解,请看可以管理时间的二叉堆(如果对堆的插入和删除不清楚,强烈建议先看堆...

    用户1260737
  • 从头到尾解析Hash 表算法

    问题描述 百度面试题: 搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为1-255字节。 假设目前有一千万个记...

    后端技术探索
  • JavaScript 数据结构与算法之美 - 归并排序、快速排序、希尔排序、堆排序

    笔者写的 JavaScript 数据结构与算法之美 系列用的语言是 JavaScript ,旨在入门数据结构与算法和方便以后复习。

    夜尽天明
  • 大数据量获取TopK的几种方案

        生活中经常会遇到求TopK的问题,在小数据量的情况下可以先将所有数据排序,最后进行遍历。但是在大数据量情况下,这种的时间复杂度最低的也就是O(NlogN...

    洋仔聊编程
  • 分治:hash + 堆 归并 快排 处理大数据

    搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为1-255字节。假设目前有一千万个记录(这些查询串的重复度比较高,虽然总数是1...

    黑白格
  • 海量数据处理 - 找出最大的n个数(top K问题)

    Tanyboye
  • 为什么每个程序员都需要学习算法?

    懂算法的程序员 ? 不懂算法的程序员 ? 算法的力量 算法是计算机科学领域最重要的基石之一,但却受到了一些程序员的冷落。 许多小伙伴看到一些公司在招聘时要求的...

    老九君
  • 典型的Top K算法_找出一个数组里面前K个最大数...或找出1亿个浮点数中最大的10000个...一个文本文件,找出前10个经常出现的词,但这次文件比较长,说是上亿行或十亿行,总之无法一次读入内存,

    http://blog.163.com/xychenbaihu@yeah/blog/static/1322296552012821103039741/

    bear_fish
  • 堆的实现及工程应用(Python)

    堆和栈是计算机程序设计中非常重要的数据结构,操作系统和数据库均有非常广泛的应用,掌握好这两种数据结构可以高效地解决很多工程问题。今天分享一下在极客专栏学到的堆的...

    somenzz
  • 面试汇总(九):数据结构与算法常见面试总结(二)——堆与栈、数组、排序

      上一篇文章我们介绍了在面试中数据结构中树的常见的面试题。这篇文章我们继续给大家介绍常见的问题。

    一计之长
  • top K 问题

    Mister24
  • 吐血整理--史上最全排序算法Python实现

    一般排序算法最常考的:快速排序和归并排序。这两个算法体现了分治算法的核心观点,而且还有很多出题的可能。

    宇宙之一粟
  • 【学习】数据分析师面试一般问些什么问题?

    罗列一些经典的问题,以飨观众O(∩_∩)O~ 1、海量日志数据,提取出某日访问百度次数最多的那个IP。 首先是这一天,并且是访问百度的日志中的IP取出来,逐...

    小莹莹
  • 面向程序员编程——精研排序算法

    这篇文章很长,我花了好久的时间(中间公司出了bug,加班了好几天( ¯ ¨̯ ¯̥̥ ))进行整理,如有任何疑问,欢迎随时留言。 关键字:排序算法,时间...

    文彬
  • 数据分析师(技术编程类)常见的10道面试题解答

    1、海量日志数据,提取出某日访问百度次数最多的那个IP。   首先是这一天,并且是访问百度的日志中的IP取出来,逐个写入到一个大文件中。注意到IP是32位的,最...

    CDA数据分析师
  • 【面试】数据分析师常见的10道面试题解答

    1、海量日志数据,提取出某日访问百度次数最多的那个IP   首先是这一天,并且是访问百度的日志中的IP取出来,逐个写入到一个大文件中。注意到IP是32位的,最...

    机器学习AI算法工程

扫码关注云+社区

领取腾讯云代金券