PHP如何实现堆排序算法的原理？

本文共计1161个文字，预计阅读时间需要5分钟。

堆（heap）是计算机科学中一种特殊的数据结构，通常可被视为一棵可看做的树形数组对象。它具有以下特点：{k1, k2, ki, ..., kn} (ki=k2i, ki=k2i + 1) | (ki=k2i, ki=k2i + 1), (i=1, 2, 3, 4...n/2) | ...。关于堆：堆中某个元素的值与其子元素值的关系取决于堆的类型，如最大堆或最小堆。

堆

堆(heap)是计算机科学中一类特殊的数据结构的统称，通常是一个可以被看做一棵树的数组对象。

堆{k1,k2,ki,…,kn} (ki <= k2i,ki <= k2i+1)|(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4...n/2)

关于堆：

• 堆中某个节点的值总是不大于或不小于其父节点的值；
• 堆总是一棵完全二叉树（下面）。
• 将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

完全二叉树

说到堆排序，就不能不提完全二叉树，这些基本概念在网上到处都是，我摘了个最简单的。。

完全二叉树：除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干结点。

我自己总结认为，正是因为有下面两个特点，

• 只允许最后一层有空缺结点且空缺在右边，即叶子结点只能在层次最大的两层上出现（存储方式的规则性）；
• 若i>1，tree的双亲为tree[i p 2]（其父子结点值的规律性）；

才使得其进行排序非常方便。