之前有篇博客（操作系统中堆和栈的区别）讲的是操作系统中的堆，顺带提了下数据结构中的堆。觉得比较简单就没详细讲解，不过这几天看排序算法看到堆排序时，感觉对堆都不怎么熟悉，有些细节问题没注意到。所以说不要小看任何一个知识点。而且经过细看才发现堆其实有很多精妙之处，怪不得很多算法都靠它来实现，如堆排序，
1. 什么是堆？
----------------------------------------------------
一句话概括：堆就是一种满足两个堆的特性的一颗二叉树。也叫优先队列
那么是满足哪两个呢？
| Binary Heap | ||
|---|---|---|
| Type | Tree | |
|
Time complexity in big O notation |
||
| Average | Worst case | |
| Space | O(n) | O(n) |
| Search | Not supported | Not supported |
| Insert | O(1) | O(log n) |
| Delete | O(log n) | O(log n) |
void Insert(int A[], int n, int t) {
n++;
A[n] = t;
int p = n;
while(p >1 && A[PARENT(p)] < t){
A[p] = A[PARENT(p)];
p = PARENT(p);
}
A[p] = t;
return max;
}
----->
----->
void GetMaximum(int A[], int n)
{
int max = A[1];
A[1] = A[n];
n--;
Max-Heapify(A, n, 1);
return max;
}BUILD-MAX-HEAP(A) 1 heap-size[A] ← length[A] 2 for i ← ?length[A]/2? downto 1 3 do MAX-HEAPIFY(A, i)
题目：输入n个整数，输出其中最小的k个。
例如输入1，2，3，4，5，6，7和8这8个数字，则最小的4个数字为1，2，3和4。
分析：这道题之前我有写过一篇关于这道题的博客（查找最小的k个元素），当时我是用的红黑树的数据结构来解决这道题的，我们都知道找出最小的k个数，我们首先利用一个容器来存储k个元素，然后遍历所有数，如果k个元素中最大数大于此时遍历的数，那么只需要替换掉最大数。当时利用红黑树来存储k个元素.同时我们如果利用最大堆的方法，也同样可以达到这样的效果。我们知道红黑树的操作与其树的高度成正比即O(logk)，同样最大堆的操作也与树的高度成正比。所以两者时间复杂度是一样的。
NYOJ412 Same binary weight 【bitset位操作】,布布扣,bubuko.com
NYOJ412 Same binary weight 【bitset位操作】
原文：http://blog.csdn.net/chang_mu/article/details/23169333