算法导论中关于堆的习题解决。6.5-8 k路链表排序 6-3Young氏矩阵
星海
posted @ 2012年11月09日 21:20
in 数据结构与算法分析
, 1296 阅读
最大/最小优先级的结构代码不再赘述，需要考虑C/C++编程中0为初始，从而在代码上修改即可。
如有需要，我会给出我的。。。
问题：6.5-8
给出一个时间为O(nlgk)，用来将k个已排序链表合并为一个排序链表的算法。n为所有输入链表中元素的总数。（提示：用一个最小堆来做k路合并）
答案：
所有比较以多路链表首元素为基数，并以此来建立最小优先级队列。
总是弹出根节点链表的首元素。每次弹出后，如果根节点已经0元素，就extract-min()，否则minHeapify()下移根节点（有可能仍是最小元素，不必小移）。
问题： 6-5
Young氏矩阵：
答案：
（1）Extract-Min()
将第一个元素保存，最后返回。
Y[m,n]（最大的）与第一个元素交换，并比较最大元素的行/列两个临近元素，取小的值与最大值交换。注意边界，递归。
(2)排序：
将每个元素放入y[m,n]，然后运行Extract-Min
n^2个元素需要2n^3的运行时间。
(3)查找：
总是与最右上角比较，如果等于，则返回。
如果大于，去除这一行
如果小于，去除这一列。。
2024年1月16日 15:20
Thanks for making the sincere attempt to explain this. I think very robust about it and want to learn more. If it’s OK, as you attain more extensive knowledge