堆 Heap

定义

堆是一种比较特殊的数据结构，可以被看做一棵树的数组对象，堆中某个节点的值总是不大于或不小于其父节点的值，堆总是一棵完全二叉树。
堆的数组表示

堆的二叉树表示法

堆的类型

最小堆-父项的密钥小于或等于子项的密钥。这称为min-heap属性。根将包含堆的最小值。
最大堆-父项的密钥大于或等于子项的密钥。这称为max-heap属性。根将包含堆的最大值。

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。 因为堆有序的特点，一般用来做数组中的排序，称为堆排序。

堆的应用

用于实现优先级队列，因为可以根据堆属性对优先级值进行排序。
可以在O（log n）时间内使用堆来实现队列功能。
用于查找给定数组中k个最小（或最大）的值。
用于堆排序算法。