堆以及堆排序

简介堆(英语:heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质: 堆中某个节点的值总是不大于或不小于其父节点的值; 堆总是一棵完全二叉树。 通常将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。 堆的存储 堆一般使用数组存储。当堆中有n个元素的时,可以将这些元素存放在数组array的前n个单元里,其中堆的根节点中元素存放在array[1]中。结点之间的

堆(英语:heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质:

  • 堆中某个节点的值总是不大于或不小于其父节点的值;
  • 堆总是一棵完全二叉树。

通常将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。

堆的存储

堆一般使用数组存储。当堆中有n个元素的时,可以将这些元素存放在数组array的前n个单元里,其中堆的根节点中元素存放在array[1]中。结点之间的关系有两种情况:

  • 如果根节点在数组中的位置是1,那么第i个位置的左右节点下标分别为2i、2i+1,父节点下标为i/2。
  • 如果根节点在数组中的位置是0,那么第i个位置的左右节点下标分别为2i+1、2i+2,父节点下标为⌊(i-1) /2⌋。


堆排序算法的C++实现 https://www.cnblogs.com/multhree/p/10507994.html

上一篇:KMP

下一篇:循环队列

新加评论 评论标题: