数据结构-堆

堆通常是一个可以被看做一棵树的数组对象。堆的具体实现一般不通过指针域，而是通过构建一个一维数组与二叉树的父子结点进行对应，因此堆总是一颗完全二叉树。对于任意一个父节点的序号n来说（这里n从0算），它的子节点的序号一定是2n+1，2n+2，因此可以直接用数组来表示一个堆。不仅如此，堆还有一个性质：堆中某个节点的值总是不大于或不小于其父节点的值。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。堆常用来实现优先队列，在面试中经常考的问题都是与排序有关，比如堆排序、topK问题等。由于堆的根节点是序列中最大或者最小值，因而可以在建堆以及重建堆的过程中，筛选出数据序列中的极值，从而达到排序或者挑选topK值的目的。

数据结构中的堆（Heap）是一种特殊的树形数据结构，可以看作是一棵完全二叉树。它的主要特点是根节点的键值是所有节点中最小（或最大）的，并且堆中每个父节点的键值都小于或等于（或大于或等于）其所有子节点的键值。

堆通常使用数组来表示，其中每个元素都对应于树中的一个节点。在数组中，父节点和子节点之间的关系可以通过下标来直接计算。例如，对于任意节点i，其父节点可以通过(i-1)/2来计算，而其左右子节点则可以通过2*i+1和2*i+2来计算。

根据根节点键值的不同，堆可以分为最小堆和最大堆。最小堆中根节点的键值是所有节点中的最小值，而最大堆中根节点的键值是所有节点中的最大值。

堆在计算机科学中有着广泛的应用，例如堆排序、优先队列、Dijkstra算法等。在这些应用中，堆通常被用来快速找到最小（或最大）元素，或者快速删除最小