数据结构与算法基础知识总结（图解数据结构堆的各种操作与算法）

在后台开发人员的面试中，有这么一个经典的题目，我们有一堆定时任务，每个任务都有执行时间，这堆定时任务还有可能会不停的增加，要求我们设计一个数据结构与算法来实现，这个题目的经典答案，就是优先队列，那么优先队列的原理是什么呢？不知道你有没有被问过这个问题，今天我们就来学习优先队列的底层原理，是一个基础数据结构，叫做堆（Heap），数据结构的堆跟内存堆栈的堆不是一回事，曾经面试一个同学，问他堆是一种什么样的数据结构，直接把内存堆栈的概念背诵出来了，真是让人可笑不得。

我们直接开门见山，数据结构中堆（Heap）是什么东西呢？这里，通常，我们讲的堆（Heap）都是二叉堆，堆是一颗完全二叉树，如果一个堆的深度为h，那么从第一层开始有1个节点，第二层有2个节点，第三层有4个节点，直到第h-1层有2^(h-2)个节点。我们把下图这种父节点小于子节点的堆称之为小根堆，反之，父节点都大于子节点的堆称之为大根堆。

数据结构堆（Heap）的最大作用就是用来排序！我们以小根堆为例(以下操作均已小根堆为例)，查询小根堆里面最小的元素，直接取第一个元素即可，算法时间复杂度为O（1）。

我们需要注意的是，一个堆如果要删除某个元素，只支持删除最顶部的元素！在堆里面，左儿子跟右儿子大小是不确定的，这个是二叉堆跟二叉排序树的一个区别（在数据结构二叉排序树中，左儿子<本身<右儿子。后面我们再来介绍下二叉排序树）。在堆中，删除头部元素称之为Pop，那么堆里面删除一个元素的算法是什么样子的呢。

我们先把最底层，最右边的元素，移到第一个元素，然后跟两个儿子比较大小，与较小的儿子交换位置因为17比65，32都小，所以把32跟17交换位置。

重复上面的算法，将32与23，45一起比较大小，23是三者之中最小，再次交换位置

重复上面的算法，将32与53进行比较，发现大小一致，不用变化

所以，我们可以把堆的Pop操作算法总结如下：跟最后一个元素交换，从树根开始，比较儿子节点，与最小的交换，直到没有儿子或者比儿子更小，算法复杂度为O(LogN)。

在堆中，插入一个元素是什么样子的呢？我们先把元素插到堆的末尾，每次都与父亲节点进行比较，如果比父亲比它小，就跟他交换位置例如下图，我们新增一个元素22，它先跟自己的父亲节点32进行比较。

重复上述算法,22再与23进行比较，随后交换位置

最后我们又得到新的小根堆，每次插入一个算法的时间复杂度为O(LogN)

堆的操作就是这么简单，支持3种操作，堆顶元素，弹出堆顶元素Pop，插入新的元素Insert。他们的算法学会了么？算法与数据结构，需要我们不停地练习，才能够熟练掌握，我会经常收集各大公司地算法面试题，分享一下经典地解题思路，有兴趣地话可以关注下我，关注下我的专栏。同名公众号（沙茶敏碎碎念）