問(wèn)答題

【簡(jiǎn)答題】在A（1：n）中存放著一個(gè)min-堆，寫(xiě)一個(gè)從堆頂A（1）刪去最小元素后將其余元素調(diào)整成min-堆的算法，要求這新的堆存放在A（1：n-1）中，且算法時(shí)間為O（logn）。

答案：

你可能感興趣的試題

問(wèn)答題

【簡(jiǎn)答題】已知n-1個(gè)元素已按min-堆的結(jié)構(gòu)形式存放在A（1），A（n-1）。現(xiàn)要將另一存放在A（n）的元素和A（1：n-1）中元素一起構(gòu)成一個(gè)具有n個(gè)元素的min-堆。對(duì)此寫(xiě)一個(gè)計(jì)算時(shí)間為O（logn）的算法。

答案：

問(wèn)答題

【簡(jiǎn)答題】
假定要把長(zhǎng)為l₁，l₂，l_n的n個(gè)程序分布到兩盤(pán)磁帶T₁和T₂上，并且希望按照使最大檢索時(shí)間取最小值的方式存放，如果存放在T₁和T₂上的程序集合分別是A和B，那么就希望所選擇的A和B使得max取最小值。一種得到A和B的貪心方法如下：開(kāi)始將A和B都初始化為空，然后一次考慮一個(gè)程序，如果，則將當(dāng)前正在考慮的那個(gè)程序分配給A，否則分配給B。證明無(wú)論是按l₁≤l₂≤，≤l_n或是按l₁≥l₂≥，≥l_n的次序來(lái)考慮程序，這種方法都不能產(chǎn)生最優(yōu)解。

答案：