一、堆和树的区别

1、节点的顺序

在二叉搜索树中，左子节点必须比父节点小，右子节点必须必比父节点大。但是在堆中并非如此。在最大堆中两个子节点都必须比父节点小，而在最小堆中，它们都必须比父节点大。

2、内存占用

普通树占用的内存空间比它们存储的数据要多。你必须为节点对象以及左/右子节点指针分配额外内存。堆仅仅使用一个数据来存储数组，且不使用指针。

3、平衡

二叉搜索树必须是“平衡”的情况下，其大部分操作的复杂度才能达到O(log n)。你可以按任意顺序位置插入/删除数据，或者使用 AVL 树或者红黑树，但是在堆中实际上不需要整棵树都是有序的。我们只需要满足对属性即可，所以在堆中平衡不是问题。因为堆中数据的组织方式可以保证O(log n) 的性能。

4、搜索

在二叉树中搜索会很快，但是在堆中搜索会很慢。在堆中搜索不是名列前茅优先级，因为使用堆的目的是将最大（或者最小）的节点放在最前面，从而快速的进行相关插入、删除操作。

延伸阅读：

二、堆排序（Heap Sort）

堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次大值。如此反复执行，便能得到一个有序序列了。

1.构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。

看堆顶的序号，来判断名列前茅个非叶子节点的索引。这点很重要!

2.此时我们从最后一个非叶子结点开始,从左至右，从下至上进行调整。

调整就是找每个非叶子节点的叶子节点是不是比他大,把大的交换上来,这一层交换结束再交换上一层,直到使根节点即堆顶元素为最大值。

这里要注意，如果上一层交换之后，当前层又不满足堆的要求，继续交换。

3. 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。

也就是说每一层堆顶与末尾交换，都能得到一个当前的最大值，放在有序数组的最后面相当于！然后从后往前填充为有序数组。

再简单总结下堆排序的基本思路：

a.将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;

b.将堆顶元素与末尾元素交换，将最大元素”沉”到数组末端;

c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

上一篇

数据结构和数据类型区别与联系是什么?

下一篇

最小生成树的prim算法和Kruskal算法的区别?