数据结构与堆排序教程图解数据结构堆的各种操作与算法

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

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

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

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

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