【读书笔记】数据结构与算法之美 第6章 堆

《数据结构与算法之美》，王争 著

标签：数据结构、算法

第6章 堆

一、堆：如何维护动态集合的最值

这一部分介绍了

• 堆的定义

• 堆的存储

• 往堆中插入元素

• 删除堆顶元素

• 删除任意元素

• 堆的性能分析

这一部分，涉及堆的基础内容，各种教材都有。作者为了体现特色，在本节加入了一个引导式问题：假设有一个动态数据集合，针对该集合，有4种操作：插入数据、按值删除数据、查询最大值和删除最大值。如何实现这样一个动态数据集合，让每个操作的时间复杂度尽可能低。答案不言而喻，作者在本节最后给出了一段分析描述。

二、堆排序：为什么说堆排序没有快速排序快

这一部分介绍了堆排序

• 堆排序之建堆

• 堆排序之排序

• 堆排序的性能分析

这一部分，涉及堆排序的主要内容，各种教材都有。作者为了体现特色，阐述了为什么说堆排序没有快速排序快，给出了两个理由。值得读一读。

三、堆的应用

这一部分介绍了堆的应用

• 优先级队列：合并多个有序文件；高性能定时器

• 求Top K：一个包含10亿个搜索关键词的日志文件，如何快速统计出Top 10热门搜索关键词

• 求中位数和百分位数

这一部分，体现了作者写本书的风格，从实用、面试和工业角度来学习数据结构和算法。几个经典的堆应用例子，是很多教材有利补充。