1. 什么是堆？ ​

堆是一种特殊的树，只要满足下面两个条件，它就是一个堆：

1. 堆是一颗完全二叉树；
2. 堆中某个节点的值总是不大于 (或不小于) 其父节点的值。

其中，我们把根节点最大的堆叫做大顶堆（或最大堆），根节点最小的堆叫做小顶堆（最小堆）。

总结 ​

• 堆是一颗完全二叉树；
• 小（大）顶堆中的每一个节点都不小于（不大于）它的父节点；
• 堆的插入、删除元素的时间复杂度都是 O(log~n~)；
• 建堆的时间复杂度是 O(n)；
• 堆排序的时间复杂度是 O(nlog~n~)；
• 堆排序的空间复杂度是 O(1)；

参考资料 ​

• 拜托，面试别再问我堆（排序）了！