本章讨论了堆
堆有两个属性1,子节点大于或等于父节点 2,树中没有洞
堆的特点是堆始终是平衡树,每个操作的复杂度都是ln(n),根节点总是最小的
堆排序的代码:
#pragma region heap int siftDown(int* buf,int pos,int len) { while(1) { int left=pos*2+1; int right=pos*2+2; int n; if(left>=len&&right>=len)break; else if(left>=len)n=right; else if(right>=len)n=left; else n=buf[left]<buf[right]?left:right; if(buf[pos]>buf[n]) { swap(buf[pos],buf[n]); pos=n; }else break; } return pos; } int siftUp(int* buf,int pos) { while(pos>0&&buf[(pos-1)/2]>buf[pos]) { swap(buf[(pos-1)/2],buf[pos]); pos=(pos-1)/2; } return pos; } void buildHeap(int* buf,int length) { for (int i=length/2-1;i>=0;i--) { siftDown(buf,i,length); } } void popRoot(int* buf,int n) { swap(buf[0],buf[n-1]); siftDown(buf,0,n-1); } #pragma endregion heap void heapSort( int* buf,int length ) { buildHeap(buf,length); for(int i=0;i<length;i++) { popRoot(buf,length-i); } }
习题:
1,2,3对堆排序进行了一些优化,使用siftDown代替siftUp,只对前n/2个元素进行操作,但是答案说这样能在O(n)复杂度下完成建堆,不能理解
4,1 构造哈夫曼树的过程需要不断地从森林中取出最小的两个节点,可以用堆实现
2 由于浮点数的表示方法,大数+小数=大数,因此需要将小数先相加,可以使用堆
3 构造一个100万个元素的最小堆,先放进去100万个元素,然后读取文件里的每个元素,如果比根节点小,跳过,反之则替换掉根节点,然后进行siftDown
4 没看懂,"每个文件中的下一个元素"是什么
5,没看明白什么是桶打包问题!
6,太妙了,这个方法可以加速链表的随即读取,但是插入的代价会变得很大
7,我的想法是每次乘以2,在i和2i中查找,如果在i和2i中,则递归直到要找的值等于i或者2i
答案很犀利,通过构造一颗平衡二叉查找树,就可以使用乘法达到二分法的效果
类似这样:
1234567
4
2 6
13 57
最终结果4261357
当然,建立树的过程需要O(n)的时间,需要使用一个元素的空间进行交换,空间需求为O(1)
8,建立一个最大堆和一个最小堆,如果新元素小于最小堆的根,则抛弃
9,没看懂题目,insert和extractmin的复杂度都是log(n)
10,没看懂题目,第二名不就是冠亚军中的亚军么?
11,