堆

逻辑结构：

　　　　　　　　　　　　　　　　　　1

　　　　　　　　　　　　　　　　  /        \

　　　　　　　　　　　　　　　　1          3

　　　　　　　　　　　　　　　/     \     /    \

　　　　　　　　　　　　　　4    　5   6      null

物理结构;

 

 

1.首先堆是一个完全二叉查找书（Complete Binary Search Tree）树，观察一下堆的逻辑结构和物理结构，逻辑结构是一颗完全二叉查找树，物理结构是一个数组.

性质：堆的实现是通过构造二叉堆，这种数据结构具有一下几个性质：

1.任意节点小于它的所有后裔，最小元素在堆的根上(堆序性)。

2.堆总是一颗完全树。(Complete Tree)

3.将根节点的最大堆叫做Max Heap,最小堆叫做Min Heap。

4.左子节点=index of parent *2+1;

5.右子节点=index of parent*2+2;

 

支持的基本操作：

1.insert:向堆中插入一个新元素：Time Complete：O（log(n));

2.update:将新元素更新使其符合堆的性质：Time Complete：O（log(n));

3.get/top:获取当前堆顶元素的值：Time Complete：O(1);

4.pop:删除堆顶元素的值：Time Complete：O（log(n));

5.heapify:使得一个Unsorted array的元素变成一个堆：时间复杂度是O（c*n）;

 

经典的算法题；

1.从没有排序的n个元素中发现最小的K个元素。

重点：面试问到这个问题，首先需要向面试官问清楚具体情况，k和n的大小关系。

 

Solution1:

使用快排排序这个元素，然后返回前K个元素。

 

Solution2:

Step1:首先建立一个最小堆  O(n);

Step2:弹出前K个最小的元素 O(klogn)；

依据上面堆的基本操作得出：Total Time Complete:O(n+klog(n))；

 

Solution3:

Step1：建立一个包含K个元素的最大堆。

Step2：循环迭代从第k+1个元素到第n个元素，然后对于当前的X；

case1:

if X<max-heap.top(),max-heap.pop(),and max-heap.insert(X);  --->log(k)

Case2:

else, do nothing;

 依据上面的堆的基本操作得出： Total Time Complete:= O(K)+O((n-k)logk);

 

Case1: k <<< a  　　　　e.g. k=20  n=1 billion

 　　O(c * n) 　　　　　　　　　　　　　O(n*(logk))

依赖于具体的情况。

Case2: k~n   　　　　　　e.g. k~0.5 billion  　　n=1 billion

　　　O(nlogn)　　　　　　　　　　　　　O(nlogn)

结论：解法2和解法3，我们很难去说哪一个更好（因为它依赖于具体的k和n的大小）.

 

Sulution4:

quick sort partition.(分区快排，直接干掉一半不需要的)

　　　　smaller　　　　　　　　　　larger

xxxxxxxxxxxxxxxxxxx　P1　xxxxxxxxxxxxxxxxxxxx　　　　　　　　　　n = 10000, k=300;

　　　　　　　　　　　pviot

 

　　smaller　　　　　　　　　　larger

 xxxxx  P2  xxxxx　　　　　　　　　　　　　　　　　　　　　　　　　n = 5000,k = 300;

　　   pivot

 

　　smaller　　　　　　　　　　larger

 xx p3 xxx　　　　　　　　　　　　　　　　　　　　　　　　　　　　n=2500 ,k=300

　pivot　　

　　　　　　　　　　　　　　　　　　　　　　　　　　　

　　smaller 　　　　　　　　　　larger     　　　　　　　　　　　　　n = 2499 ,k = 299

x p4 xxxxx

Quick partiotion:

worst case:O(n*2)

Average case:O(n)　　　　　　　　　　　　n+n/2+n/4+n/8;