6.1-1 堆中高度的定义为root到叶子节点最长简单下降路径上边的数目 2^h<= n <= 2^(h+1) -1
6.1-2 2^h<= n <= 2^(h+1) -1
==> lg(n) <=h <= lg(n+1)-1
==> lg(n)取下整
6.1-3 反证
6.1-4 叶子节点
6.1-5 是
6.1-6 否
6.1-7 未知
6.2.1 略
6.2.2 略
6.2.3 直接返回，不做修改
6.2.4 不做修改
6.2.5
void max_heapify(A,i) { while (true) { int l = i*2; int r = i*2 + 1; largest = max(A[i],max(A[l], A[r]))的下标; if (largest == i) break; swap(A[i],A[largest]); i = largest; } }
6.2.6 最坏情况就是从root到叶子节点每一层都要进行一次调整，那么最坏的复杂度就是从root到叶子节点的高度lgn
6.3.2 无法保证root为最大，比如{5，4，3，12}
6.5.6 FIFO队列：增加一个全局counter，每次增加一个元素counter+1，并且堆是按照counter大小作为关键字。栈可以做相应-1操作。
6.5.7 heap_delete实现
思路：分三种情况考虑
1）要删除的A[i]比最后一个元素大则交换后向下调整O(lgn)
2）要删除的A[i]比最后一个元素小则向上调整O(lgn)
3）相等不处理O(1)
void heap_delete(A,i){ swap(A[heap_size], A[i]); if (A[heap_size] == A[i]) { // do nothing } else if (A[heap_size] > A[i]) { max_heapify(A,i); } else { increate_key(A, i, A[i]); } head_size —; }
6.5.8
思路： 有k个有序数组，取每个数组的第一个元素建立一个节点数为k的堆，这样每次操作堆的复杂度为lnk，一共n个元素这样把所有n个元素都放在堆里进行一次调整总体复杂度为O(nlnk),伪码：
merge_list(vector<vector<struct node*> > list) { vector<int> result; //建堆 for (int i=0; i<list.size(); ++i) { min_heap[i] = list[i][0]; } build_min_heap(min_heap); //n次循环直到堆中无元素 while(n—) { result.push_back(min_heap[0]); min_heap_delete(min_heap, 0); //取出堆顶元素对应链表的next元素并加入堆中 //如果对应链表中已无元素，则调整堆的大小 if next_data != NULL min_heap_insert(min_heap, next_data); } return result; }