本文目录导航：
数据结构与算法--堆和堆排序
堆排序是一种原地的、期间复杂度为 O(nlogn) 的排序算法。
堆是一种不凡的树。 只需满足这两点，它就是一个堆：
关于每个节点的值都大于等于子树中每个节点值的堆，咱们叫做 “大顶堆” 。
关于每个节点的值都小于等于子树中每个节点值的堆，咱们叫做 “小顶堆” 。
齐全二叉树比拟适宜用数组来存储。
用数组来存储齐全二叉树是十分节俭存储空间的。
下标可以间接计算出左右字数的下标。
（数组中下标为 i 的节点，左子节点下标为 i∗2 ，右子节点下标为 i∗2+1，父节点的下标为 i/2 。
）
假设咱们把新拔出的元素放到堆的最后，你可以看我画的这个图，是不是不合乎堆的个性了？于是，咱们就须要启动调整，让其从新满足堆的个性，这个环节咱们起了一个名字，就叫做 堆化（heapify） 。
堆化实践上有两种，从下往上和从上往下。
这里我先讲从下往上的堆化方法。
堆化十分方便，就是顺着节点所在的门路，向上或许向下，对比，而后替换。
咱们把最后一个节点放到堆顶，而后应用雷同的父子节点对比方法。
关于不满足父子节点大小相关的，调换两个节点，并且重复启动这个环节，直到父子节点之间满足大小相关为止。
这就是 从上往下的堆化方法 。
一个蕴含 n 个节点的齐全二叉树，树的高度不会超越 log2n。
堆化的环节是顺着节点所在门路比拟替换的，所以堆化的期间复杂度跟树的高度成正比，也就是 O(logn)。
拔出数据和删除堆顶元素的关键逻辑就是堆化，所以，往堆中拔出一个元素和删除堆顶元素的期间复杂度都是 O(logn)。
这里咱们借助于堆这种数据结构成功的排序算法，就叫做堆排序。
这种排序方法的期间复杂度十分稳固，是 O(nlogn)，并且它还是原地排序算法。
从后往前处置数组，并且每个数据都是从上往下堆化。
由于叶子节点往下堆化只能自己跟自己比拟，所以咱们间接从最后一个非叶子节点开局，依次堆化就行了。
建堆的期间复杂度就是 O(n)。 推导环节见 极客期间--数据结构与算法之美
建堆完结之后，数组中的数据曾经是依照大顶堆的个性来组织的。
数组中的第一个元素就是堆顶，也就是最大的元素。
咱们把它跟最后一个元素替换，那最大元素就放到了下标为 n 的位置。
这个环节有点相似下面讲的“删除堆顶元素”的操作，当堆顶元素移除之后，咱们把下标为 n 的元素放到堆顶，而后再经过堆化的方法，将剩下的 n−1 个元素从新构建成堆。
堆化成功之后，咱们再取堆顶的元素，放到下标是 n−1 的位置，不时重复这个环节，直到最后堆中只剩下标为 1 的一个元素，排序上班就成功了。
整个堆排序的环节，都只须要极一般暂时存储空间，所以堆排序是原地排序算法。
堆排序包括建堆和排序两个操作，建堆环节的期间复杂度是 O(n)，排序环节的期间复杂度是 O(nlogn)，所以，堆排序全体的期间复杂度是 O(nlogn)。
堆排序不是稳固的排序算法，由于在排序的环节，存在将堆的最后一个节点跟堆顶节点调换的操作，所以就有或许扭转值相反数据的原始相对顺序。
堆这种数据结构几个十分关键的运行：优先级队列、求 Top K 和求中位数。
假定咱们有 100 个小文件，每个文件的大小是 100MB，每个文件中存储的都是有序的字符串。
咱们宿愿将这些 100 个小文件兼并成一个有序的大文件。
这里就会用到优先级队列。
这里就可以用到优先级队列，也可以说是堆。
咱们将从小文件中取进去的字符串放入到小顶堆中，那堆顶的元素，也就是优先级队列队首的元素，就是最小的字符串。
咱们将这个字符串放入到大文件中，并将其从堆中删除。
而后再从小文件中取出下一个字符串，放入到堆中。
循环这个环节，就可以将 100 个小文件中的数据依次放入到大文件中。
咱们可以用优先级队列来处置。
咱们依照义务设定的口头期间，将这些义务存储在优先级队列中，队列首部（也就是小顶堆的堆顶）存储的是最先口头的义务。
如何在一个蕴含 n 个数据的数组中，查找前 K 大数据呢？咱们可以保养一个大小为 K 的小顶堆，顺序遍历数组，从数组中取出数据与堆顶元素比拟。
假设比堆顶元素大，咱们就把堆顶元素删除，并且将这个元素拔出到堆中；假设比堆顶元素小，则不做处置，继续遍历数组。
这样等数组中的数据都遍历完之后，堆中的数据就是前 K 大数据了。
中位数，望文生义，就是处在两边位置的那个数。
经常使用两个堆：一个大顶堆， 一个小顶堆。
小顶堆中的数据都大于大顶堆中的数据。
假设新添加的数据小于等于大顶堆的堆顶元素，咱们就将这个新数据拔出到大顶堆；否则，咱们就将这个新数据拔出到小顶堆。
也就是说，假设有 n 个数据，n 是偶数，咱们从小到大排序，那前 2n 个数据存储在大顶堆中，后 2n 个数据存储在小顶堆中。
这样，大顶堆中的堆顶元素就是咱们要找的中位数。
假设 n 是奇数，状况是相似的，大顶堆就存储 2n+1 个数据，小顶堆中就存储 2n 个数据。
极客期间--数据结构与算法之美--28 | 堆和堆排序：为什么说堆排序没有极速排序快？
如何评估极客期间上王争的「数据结构与算法之美」的爆火？
在极客期间平台上，王争的《数据结构与算法之美》一书为何备受注目并引发热议？
时代似乎在向咱们收回信号：在这个消息爆炸的时代，虽然实体书如亚马逊上的《数据结构与算法之美》以74元的亲民多少钱和黑白版面吸引着眼球，但面对海量的在线课程，人们似乎更偏差于听觉的方便。
付费课程，尤其是王争的解说，似乎为那些盼望常识但又不愿静下心来浏览的听众提供了一剂“心灵鸦片”。
他们花钱凝听，似乎在短期间内找到了处置疑问的捷径，似乎焦虑症患者持久地沉迷在“治愈”之中。
但是，这种持久的满足感并不能代替深入学习，事实的应战和下一次性的焦虑依然期待着他们。
《数据结构与算法之美》的魅力在于它将复杂的实践常识转化为活泼的故事，让听者在轻松的气氛中领略算法的精妙。
但是，书籍的浏览体验却不可被方便地同等于听觉教授。
书籍的深度和系统性，是那些情愿静心研读的人能力收获的宝藏。
在当今快节拍的社会，如何在听与读之间找到平衡，成为了一个值得讨论的疑问。
虽然在线听书在某种水平上满足了公众的即时需求，但它并不能代替对常识的深化了解和常年积攒。
真正的学习，是须要期间和耐烦去积淀的，就像那本静静躺在书架上的黑白算法书，期待着有心人的打开和探求。
所以，王争的课程或许能暂时缓解咱们的焦虑，但唯有真正去把握和运用那些“算法之美”，能力在常识的陆地中游刃缺乏，抵御下一次性的应战。
数据结构的来源作用和意义
“数据结构”作为一门独立的课程在国外是从1968年才开局设立的。
1968年美国唐纳德·克努特（Donald Ervin Knuth）教授开创了数据结构的最后体系，所著的《计算机程序设计艺术》第一卷《基本算法》是第一本较系统地论述数据的逻辑结构和存储结构及其操作的著述。
“数据结构”在计算机迷信中是一门综合性的专业基础课，数据结构是介于数学、计算机配件和计算机软件三者之间的一门外围课程。
数据结构这一门课的内容不只是普通程序设计（特意是非数值性程序设计）的基础，而且是设计和成功编译程序、操作系统、数据库系统及其余系统程序的关键基础。
普通以为，一个数据结构是由数据元素依据某种逻辑咨询组织起来的。
对数据元素间逻辑相关的形容称为数据的逻辑结构；数据必定在计算机内存储，数据的存储结构是数据结构的成功方式，是其在计算机内的示意；
此外讨论一个数据结构必定同时讨论在该类数据上口头的运算才无心义。
一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处置的效率。
在许多类型的程序的设计中，数据结构的选用是一个基本的设计思考起因。
许多大型系统的结构阅历标明，系统成功的艰巨水平和系统结构的品质都重大的依赖于能否选用了最优的数据结构。
许多时刻，确定了数据结构后，算法就容易获取了。
有些时刻事情也会反上来，咱们依据特定算法来选用数据结构与之顺应。
不论哪种状况，选用适宜的数据结构都是十分关键的。
选用了数据结构，算法也随之确定，是数据而不是算法是系统结构的关键起因。
这种洞见造成了许多种软件设计方法和程序设计言语的产生，面向对象的程序设计言语就是其中之一。
裁减资料
数据指对主观事情启动记载并可以甄别的符号，是对主观事物的性质、形态以及相互相关等启动记载的物理符号或这些物理符号的组合。
它是可识别的、形象的符号。
它不只指狭义上的数字，还可以是具备必定意义的文字、字母、数字符号的组合、图形、图像、视频、音频等，也是主观事物的属性、数量、位置及其相互相关的形象示意。
例如，“0、1、2...`”、“阴、雨、降低、气温”“在校生的档案记载、货物的运输状况”等都是数据。
数据经过加工后就成为消息。
在计算机迷信中，数据是指一切能输入到计算机并被计算机程序处置的符号的介质的总称，是用于输入电子计算机启动处置，具备必定意义的数字、字母、符号和模拟量等的通称。
如今计算机存储和处置的对象十分宽泛，示意这些对象的数据也随之变得越来越复杂。
