堆的定义
堆（英语：heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：堆中某个节点的值总是不大于或不小于其父节点的值；堆总是一棵完全二叉树。
大根堆
将根节点最大的堆叫做最大堆或大根堆，在这颗完全二叉树中,所有根节点都大于两个子节点. 
小根堆
根节点最小的堆叫做最小堆或小根堆。在这颗完全二叉树中,所有根节点都小于两个子节点. 
堆的定义如下：
n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时，称之为堆。 小根堆: (ki <= k2i,ki <= k2i+1)或者 大根堆: (ki >= k2i,ki >= k2i+1), (i = 1,2,3,4…n/2)
堆排序
给定一个大根堆的二叉树. 每次将堆顶元素取出, 放入有序集合. 将堆低元素放入堆顶,重新将该树构造大根堆,重复上诉过程,即可得到一个有序集合.
算法思路:
- 构造大根堆.
- 取堆顶元素(即最大值)放入有序集合中, 将堆低元素放入堆顶,此时该二叉树可能不满足堆,故需要重新构建堆.
- 重复步骤2,直到构造完成.
代码实现:
/**
* 调整堆
* @param poi 需要调整的数字位置 *
* @param a 数组-> 模拟堆 *
* @param len 数组长度, 堆元素个数
* */
public static void adjustHeap(int poi, int a[], int len){
int temp = a[poi];
for (int i = poi*2+1; i < len; i=i*2+1) {
if (i+1 < len && a[i] < a[i+1]) {
i++;
}
if(temp < a[i]){
a[poi] = a[i];
poi = i;
}else {
break;
}
}
a[poi] = temp;
}
/** * 堆排序 *
* @param a 数组-> 模拟堆 *
* @param len 数组长度, 堆元素个数
* */
public static void heapsort(int a[], int len){
for(int i = len/2-1; i >= 0; i--){
adjustHeap(i, a, len);
}
for(int i = len-1; i > 0; i--){
int temp = a[0];
a[0] = a[i];
a[i] = temp;
adjustHeap(0, a, i);
}
}
构造大根堆分析:
由于二叉树的叶子节点数为: n0 = (n+1)/2 //该除2是不会计算小数,也就是计算机中的除2 所以非叶子节点树为: n1 = n - n0 = n/2. //在计算机语言中是n/2 由于数组是从0开始, 所以我们需要构造大根堆时是从n/2 -1 到 0,即构造所有非叶子节点.
算法分析:
时间复杂度: O(nlog(n)) 总时间复杂度: O(nlog(n)) 初始化大根堆时间复杂度分析:
树的深度: k = log(n) => 2^k = n
最坏的情况在第i层 有2^(i-1) 个节点, 往下k-i次替换. 所以时间复杂度:
s = 2^(i-1) * (k-i) | i -> (k-1 ~ 1)
展开: s = 2^(k-2) * 1 + 2^(k-3) * 2 + 2^(k-4) * 3 + … + 2^0 * (k-1)
两边同时乘2: 2s = 2^(k-1) + 2^(k-2) * 2 + 2^(k-3) * 3 + … + 2^1 * (k-1)
2式减1式: s = (2^(k-1) + 2^(k-2) + 2^(k-3) + … + 2^1) - (k-1) = 2*(1-2^(k-1))/(1-2) - (k-1) = 2^k - k - 1
所以s的时间复杂度: n - log(n) - 1 => O(n)
总时间复杂度: 循环n-1次,最坏的情况每次都从1到k, 每层都换,也就是log(n)次, 所以时间复杂度为: (n-1) * log(n) 所以总时间复杂度: O(nlog(n)). 空间复杂度:O(1) 稳定性: 不稳定的排序算法.
作用:
堆排序可以用来排序, 但大多数时候不如快排 可是当数据量巨大, 如百万级别的时候, 快排的递归调用可能会使堆栈溢出.而堆排序O(1)的空间复杂度,还没有递归调用, 就十分合适了. 还可以用来实现优先队列.