Heap(堆)的基础知识入门

逻辑结构:

                  1

                  /        \

                1          3

               /     \     /    \

              4     5   6      null

物理结构;

Heap(堆)的基础知识入门

 

 

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;

 

  

 

上一篇:CM: How to get the complete url of a product attachment


下一篇:1064 Complete Binary Search Tree (30 分)