堆與互不相交集課件(編輯修改稿)
2025-08-17 13:47 本頁面
【文章內(nèi)容簡介】 。因此算法需要 時間和 空間構(gòu)造一個 n元素的堆。 堆 )(n? )1(?（ 4）堆排序 算法 HEAPSORT 輸入： n個元素的數(shù)組 H[1… n] 輸出：以非降序排列的數(shù)組 A 1 MAKEFEAP(A) 2 for j=n downto 2 3 互換 A[1]和 A[j] 4 SIFT_DOWN(A[1… j1],1) 5 end for 定理 ： 算法 HEAPSORT對 n元素排序要用 時間和 空間。 堆 )log( nn?)1(?（ 5）最大堆和最小堆 （ 1）不相交集數(shù)據(jù)結(jié)構(gòu) _等價類的劃分 ? 問題提出 在很多應(yīng)用中，經(jīng)常把 n個元素劃分成若干集合，然后，把某兩個集合合并一個集合，或者尋找包含某特定元素的集合。如對集合 定義如下的等價關(guān)系： 求 S關(guān)于 R的等價類，其中， %表示求模運算。 ? 求 S關(guān)于 R的等價類運算如下： 初始化： {1}{2}{3}{4}{5}{6}{7}{8} 1R4，有： {1， 4} {2}{3}{5}{6}{7}{8} 4R7，有： {1， 4,7} {2}{3}{5}{6}{8} 2R5，有： {1， 4， 7} {2， 5}{3}{6}{8} 不相交集 }8,2,1{ ??s}03)%(|,{ ????????? xySySxyxR 5R8，有： {1， 4， 7} {2， 5， 8}{3}{6} 3R6，有： {1， 4， 7} {2， 5， 8}{3， 6} 上述可見，運算需要兩個操作：一是尋找 x， y所在的集合；二是合并兩個已知的集合。 ? 基本概念 數(shù)據(jù)結(jié)構(gòu)：用一維數(shù)組表示各個子集合組成的森林。每 棵樹表示一個子集。 樹根節(jié)點：無父節(jié)點，置為 0； 孩子節(jié)點：指向父節(jié)點，置為父節(jié)點下標。 如：集合 {1， 2， 3， 4， 5， 6， 7， 8， 9， 10， 11}的下一個劃分： {1， 7， 10， 11}， {2， 3， 5， 6}， {4，8}和 {9} 。 不相交集 ? 基本運算 FIND(x)：尋找并返回元素 x的集合名字，即樹根。 UNION(x， y)：合并 x， y所在的兩個集合，并集名取自 x或 y所在集合名稱。 不相交集 0 3 0 8 2 2 1 0 0 1 1 1 2 3 4 5 6 7 8 9 10 11 1 7 10 11 3 2 5 6 8 4 9 顯然，運算 UNION缺點是使樹退化為線性結(jié)構(gòu)。這樣，在 n次尋找運算的代價是： 不相交集 )(2 )1(12)1( 2nnnnn ????????? ? 為此，應(yīng)該修正運算 UNION運算，這導(dǎo)致一些新概念的產(chǎn)生。 設(shè) x
法律信息相關(guān)推薦
鄂ICP備17016276號-1