星海's Blog

老头初学编程
单链表,双向链表,栈ADT
计数排序和基数排序的实现。。

算法导论中关于堆的习题解决。6.5-8 k路链表排序 6-3Young氏矩阵

星海 posted @ 2012年11月09日 21:20 in 数据结构与算法分析 , 1046 阅读

最大/最小优先级的结构代码不再赘述,需要考虑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)查找:

总是与最右上角比较,如果等于,则返回。

如果大于,去除这一行

如果小于,去除这一列。。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter