Software Learning Resource Service Platform CHAPTER 7 搜尋和排序 (Search and Sort) 1.

Slides:



Advertisements
Similar presentations
Course 1 演算法: 效率、分析與量級 Algorithms: Efficiency, Analysis, and Order
Advertisements

基本概論 Basic concepts.
Chapter 10 搜尋(search).
Introduction 基本概念 授課老師:蕭志明
Chapter 3 The Fundamentals : Algorithms, the Integers, and Matrices
第5章 排序与查找 PART A 《可视化计算》.
数据结构(C语言版) Data Structure
Performance Evaluation
第十章 内部排序 10.1 概述 10.2 插入排序 直接插入排序 其他插入排序 希尔排序
性別透視鏡 鳳鳴電台 高宜君老師.
Tree(樹) 什麼是「樹」? 「樹」的範例 「樹」的定義 「樹」的表示法.
課程名稱:資料結構 授課老師:_____________
分治演算法 各個擊破獲得最後勝利 國立中央大學 資工系 江振瑞 教授.
Chapter 4 歸納(Induction)與遞迴(Recursion)
主讲人: 吕敏 { } Spring 2012 ,USTC 算法基础 主讲人: 吕敏 { } Spring 2012 ,USTC.
計算方法設計與分析 Design and Analysis of Algorithms 唐傳義
樹狀結構 陳怡芬 2018/11/16 北一女中資訊專題研究.
第九章 排序 概述 插入排序 交换排序 选择排序 归并排序 基数排序 外排序.
Chapter 6 Graph Chang Chi-Chung
Course 4 搜尋 Search.
排序 Sorting.
快速排序法 (Quick Sort).
第9章 排序.
第十章 排序與搜尋.
C 程式設計— 控制敘述 台大資訊工程學系 資訊系統訓練班.
搜尋資料結構 Search Structures.
演算法方式總覽 The Divide-and-Conquer Strategy (個各擊破)(binary Searching、Quick Sort…. ) The Greedy Method(貪婪演算法) (Prim MST、Kruskal MST、Djikstra's algorithm) Dynamic.
Data Structure(資料結構) 授課老師: 蕭志明 助理教授 Ext:6779
程式撰寫流程.
演算法與資料結構 製作單位: 高雄市立高雄中學.
圖表製作 集中指標 0628 統計學.
重點 資料結構之選定會影響演算法 選擇對的資料結構讓您上天堂 程式.
基數排序法.
Sorting 排序 Bubble Sort O(n2) Insert Sort Selection Sort Quick Sort
Data Structure.
计算机问题求解 – 论题2-14 -B树 2018年6月10日.
数据结构 Data Structure CSU 主讲人:王国军,郑瑾 中南大学信息院计科系
樹 2 Michael Tsai 2013/3/26.
感謝同學們在加分題建議. 我會好好研讀+反省~
B+ Tree.
Chapter 5 Recursion.
Sorting in Linear Time Michael Tsai 2013/5/21.
鄧姚文 資料結構 第一章:基本概念 鄧姚文
Week 2: 程式設計概念與 演算法的效能評估
Total Review of Data Structures
資料結構與C++程式設計進階 排序與搜尋 講師:林業峻 CSIE, NTU 6/ 14, 2010.
软件工程 第四章 软件设计 软件过程设计技术与工具.
计算机算法基础 周中成 苏州科技学院应用数学系 2019/4/18.
3.5 Region Filling Region Filling is a process of “coloring in” a definite image area or region. 2019/4/19.
第8章 資料排序 資料結構設計與C++程式應用
软件设计任务 从工程管理的角度来看,软件设计分两步完成。 概要设计,将软件需求转化为数据结构和软件的系统结构。
第九章 排序 概述 插入排序 快速排序 交换排序(起泡排序) 选择排序 归并排序.
Hashing Michael Tsai 2013/06/04.
计算机问题求解 – 论题 算法方法 2016年11月28日.
软件测试技术-白盒测试 张志强 2006.
Course 10 削減與搜尋 Prune and Search
99高中資訊科選修課程 夥伴學習教師 專業進修研習 進階程式設計--演算法 教學示例與研討
講師:郭育倫 第2章 效能分析 講師:郭育倫
算法导论第一次习题课.
第九章 运行时存储空间组织 网上教学系统: : 编译原理
演算法分析 (Analyzing Algorithms)
累堆排序法 (Heap Sort).
唐常杰 四川大学计算机学院 计算机科学技术系
Hashing Michael Tsai 2017/4/25.
本教學投影片係屬教科書著作之延伸,亦受著作權法之保護。
資料結構 老師:李崇明 助教:楊斯竣.
顺序查找与二分查找复习.
Data Structure.
排序 排序(sorting)是计算机程序设计中的一种重要操作,它的功能是将一个数据元素(或记录)的任意序列,重新排列成一个按关键字有序的序列。 由于待排序的记录数量不同,使得排序过程中涉及的存储器不同,可将排序方法分为两大类:一类是内部排序,指的是待排序记录存放在计算机存储器中进行的排序过程;另一类是外部排序,指的是待排序记录的数量很大,以致内存一次不能容纳全部记录,在排序过程中对外存进行访问的排序过程。
JAVA 程式設計與資料結構 第十七章 Tree.
Presentation transcript:

Software Learning Resource Service Platform CHAPTER 7 搜尋和排序 (Search and Sort) 1

Software Learning Resource Service Platform Search 分類 : Ⅰ. Internal( 內部 ) v.s External search( 外部 ) 內部 : 資料量少,可直接置於記憶體中進行搜尋 外部 : 資料量太大,無法一次置於記憶體,通常 儲存於輔助記憶體中 (Disk 、 Tape) ,再分 批載入進行 search Ⅱ. Static( 靜態 ) v.s Dynamic search( 動態 ) 資料庫中 data 變動程度低、高 2

Software Learning Resource Service Platform Search Ⅲ. Partial key( 部分鍵值 ) v.s whole key search( 整 個鍵值 ) Ⅳ. Actual key v.s Transformation key 之搜尋 Search 可分成四種 : Linear Search Binary Search Fibonacci Search Interpolation Search 3

Software Learning Resource Service Platform Linear Search If list has n records, with list[i].key referring to the key value for record i, then we can search the list by examining the key values list[0].key,…,list[n-1].key, in that order, until the correct record is located, or we have examined all the records in the list. Since we examine the records in sequence, this searching technique is known as a sequential search. 平均比較次數 次 n-2n-1n …… 4

Software Learning Resource Service Platform Binary Search  二元搜尋 (Binary Search) 是找尋一個排序過的檔案,觀念 與二元樹十分類似,需要藉助〝 Random Access 〞機制支 援才可。  This search begins by comparing searchnum and list[middle].key where middle =.There are three possible outcomes: searchnum < list[middle].key:In this case, we discard the records between list[middle] and list[n-1], and continue the search with the records between list[0] and list[middle-1]. 5

Software Learning Resource Service Platform searchnum = list[middle].key: In this case, the search terminates successfully. searchnum > list[middle].key: In this case, we discard the records between list[0] and list[middle] and continue the search with the records between list[middle+1] and list[n-1]. 6 Binary Search

Software Learning Resource Service Platform Procedure BinSearch (f: afile ; var i:integer ; n,k:integer) Var done : boolean ; l,u,m: integer ; Begin l:=1 ; u:=n ; i:=0 ; done:=false ; while ((l<=u) and(not done)) do Begin m:=(l+u) div 2 ; case compare( k, f[m].key) of 〝 > 〞 : l := m+1 {Look in upper half} 〝 = 〞 : Begin i:=m ; done:= true ; End ; 〝 < 〞 : u:=m-1 ; {Look in lower half} end ; {of case} End ; {of while} End ; {of BinSearch} 7 Binary Search

Software Learning Resource Service Platform 12 筆,畫出 Decision tree 8

Software Learning Resource Service Platform Binary Search 二元搜尋法 : 需符合 (1) 檔案中的紀錄必須事先排序過 (2) 檔案是可以 Direct Access file 或 Random file 2.Time Complexity ∵ T(n) = T(n/2)+1 , T(1) = 1 ∴ T(n) = O( ) 3. 一般而言, n 值小適合 Sequential Search n 值大適合 Binary Search 9

Software Learning Resource Service Platform Fibonacci Search 費式數列 F 0 =0 , F 1 = 1 , F i = F i-1 +F i-2,i ≧ 2 0,1,1,2,3,5,8,13,21,34,55,… 公式 : 〝 F a +m = n+1 〞 (1)n: 紀錄個數 (2)F a : 是≦ n+1 之最大費氏數 (3)m: 是≧ 0 之正整數 先求出 F a ,在求出 m (m=(n+1)-F a ) 。 10

Software Learning Resource Service Platform Fibonacci Search (1)n= 33 筆,則 F a = ? m = ? Steps 1. 找≦ n+1= ≦ 34 之最大費氏數 → F 9 Steps 2.m= (n+1)-F a = 34-34=0 n FnFn

Software Learning Resource Service Platform Fibonacci Search 優點 :  只需用到加法與減法而不必用到除法  在平均情況,它的平均搜尋次數少於二分搜尋法 缺點 :  每次必須去求算下一個費氏數  最壞情況,它的平均搜尋次數多於二分搜尋法 12

Software Learning Resource Service Platform Interpolation Search 內插 ( 插補 ) 搜尋的方法是拿 與 相比較,其 中 : f[u].key , f[l].key 分別是檔案中最大與最小的鍵值 比較 (k, f[l].key) 〝 = 〞 : 找到 〝 < 〞 :u=(l+i)-1 〝 > 〞 :l=(l+i)+1 13

Software Learning Resource Service Platform Interpolation Search 其好壞完全依鍵值的分布而定,在 uniform 分佈時有 最好的效果,在 n>500 時且鍵值為 uniform distribution 時,效果比二元搜尋法還要好 被搜尋的檔案仍需要滿足二個條件 : (1) 檔案中的紀錄必須事先經過排序 (2) 必須是 Direct Access 或 Random access 機制支援 14

Software Learning Resource Service Platform Sorting 定義 : 排序是指將某一群資料按照某一種排列的規則,重新 安排此群資料的次序 (order) 使其形成遞增 ( 或遞減 ) 的 線性次序關係 (Linear Order) 。 對於兩個鍵值 k(i)= k(j) 的紀錄 r(i) 和 r(j) ,如果在原始 檔案中, r(i) 排在 r(j) 之前;而在排序後,檔案中的 r(i) 仍在 r(j) 之前,則稱此排序有穩定性 (stable) 。反之, 如果 r(j) 在 r(i) 之前,則稱此排序為不穩定 (unstable) 15

Software Learning Resource Service Platform Insertion Sort 26 、 5 、 49 、 13 、 6 寫出排序過程 Ans: (1)5 、 26 、 49 、 13 、 6 (2)5 、 26 、 49 、 13 、 6 (3)5 、 13 、 26 、 49 、 6 (4)5 、 6 、 13 、 26 、 49 16

Software Learning Resource Service Platform Algorithm (1)Insert(r, A[ ],i) 副程式 (2)Insort(A[ ],n) 主程式 (1) Procedure Insert(r, A[ ], i)// 將紀錄 r 插入到 A[0]~A[i] 已排序好 之串列中 // Var j : integer ; Begin j:= i ; While r.key<list[j].key Do Begin list[j+1]:=list[j] ; j:= j-1 ; End ; List[j+i]:= r ; End ; 17

Software Learning Resource Service Platform (2) Procedure Insort(Var list : afile ; n:Integer) ; Var j: Integer ; Begin list[0].key:=-∞ ; for j:= 2 to n do insert (list[j], list, j-1) ; End ; 18

Software Learning Resource Service Platform Insertion Sort Ⅰ. Time complexity : worst case 與 average case = O( ) , best case( 已 照順序排列好者 ) 為 O(n) ,因為只需 n-1 次的比較。 Ⅱ. 插入排序法是穩定的。 e.g ……5… … 排序後 :……5…… … Ⅲ. Space Complexity = O(1) → 僅須固定空間,一為 Dummy Record ,一為 r 變數。 19

Software Learning Resource Service Platform Selection Sort 觀念 : 令在 n 個紀錄裡 R 1, R 2, …, R n ,其鍵值分別為 K 1,K 2,…,K n 欲將這個 n 個紀錄由小到大排列時,則須 執行以下兩個步驟 : ( 一 ) 在所有紀錄中挑選一個具有最小鍵值的記錄然 後將此紀錄與第 i 個位置對調。 ( 二 ) 在剩餘的 n-1 個紀錄中,再次挑選一個具有最小 鍵值的記錄, i 值加 1 ,然後將此紀錄與第 i 個紀錄位 置對調,重複進行步驟 ( 二 ) 直到 i=n 為止。 20

Software Learning Resource Service Platform Procedure SelectSort(R,n) Begin For i:= 1 to n-1 do Begin m := i ; For j = i+1 to n do If k j <k m then m :=j ; End ; {of For loop} If i m then Begin Swap (R i,R m ) ; End ; End ; {of SelectSort} 21 Selection Sort

Software Learning Resource Service Platform Selection Sort Ⅰ. Time complexity: Best 、 Average 、 Worst case 為 O( ) Ⅱ. Space complexity : O(1) Ⅲ. 不穩定排序 (unstable sort) e.g. pass1: pass2: 22

Software Learning Resource Service Platform Bubble Sort 觀念 : Bubble sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. e.g. 26 、 5 、 47 、 19 、 6 寫出排序過程 pass1 :5 、 26 、 19 、 6 、 47 pass2 :5 、 19 、 26 、 6 、 47 pass3 :5 、 6 、 19 、 26 、 47 pass4 :5 、 6 、 19 、 26 、 47 23

Software Learning Resource Service Platform Procedure BubbleSort(R, n) Begin for i=1 to (n-1) do begin f = 0; for j=1 to (n-1) do if R[j+1].key<R[j].key then [swap(R j, R j+1 ); f=1; ] if f=0 then exit // No swap: exit// end; End; {of BubbleSort} 24

Software Learning Resource Service Platform Bubble Sort Ⅰ. Time complexity : Best case : O(n) Worst case : O( ) Average case : O( ) Ⅱ. 為一 stable sort Ⅲ. Space complexity : O(1) 例 : 給予 1 、 2 、 3 、 4 、 5 由小到大排序 → i=1 j 從 1 to n-1 do 比較 (if k j+1 <k j ) 結果無一次成立,故 f 仍為 0 ,所以 exit → 只作 n-1 次比較,但無任何 swap 故為 best case = O(n) 25

Software Learning Resource Service Platform Shell Sort 觀念 :( 版本一 ) 比較第 i 筆與第 [i+span] 筆記錄,若前者 > 後者,則 swap( 前、後 ) ,每回合須持續作到無 swap 發生,才可 停止,以便進入下一回合 ( 回合數依 span 型而定 ) 。 Note: 常見的型有  型 ( 、 )  型  自定型 ( 但最後一回合 span 須為 1) 26

Software Learning Resource Service Platform 26 、 5 、 3 、 8 、 10 、 12 、 1 、 2(span = ) Ans: pass 1: span=[8/2]=4 (1)(2)(3)(4)(5)(6)(7)(8)

Software Learning Resource Service Platform pass 2: span= [4/2]= 2 28 (1)(2)(3)(4)(5)(6)(7)(8) pass 3: 由小到大小寫出即可 span=2/2=1

Software Learning Resource Service Platform ( 版本二 ) 若此回合 span 值 =k ,則表示有 k 條 sublists( 長度約 n/k) 要執行 Insertion sort 給予 30 、 15 、 2 、 8 、 19 、 47 、 3 、 9 、 11 、 6 執行 shell sort (span=5 , 3 , 1) Pass 1. Span=5 (1) 跟 (6) , (2) 跟 (7) , (3) 跟 (8) , (4) 跟 (9) , (5) 跟 (10) 比較則會變成 → 30 、 3 、 2 、 8 、 6 、 47 、 15 、 9 、 11 、 19 (1)(2)(3)(4)(5)(6)(7)(8)(9)(10)

Software Learning Resource Service Platform Pass 2. Span= 3 (1) 跟 (4) 、 (4) 跟 (7) 、 (7) 跟 (10) 比較 (2) 跟 (5) 、 (5) 跟 (8) 比較 (3) 跟 (6) 、 (6) 跟 (9) 比較 得到 8 、 3 、 2 、 15 、 6 、 11 、 19 、 9 、 47 、 30 Pass 3. Span=1 (1)(2)(3)(4)(5)(6)(7)(8)(9)(10)

Software Learning Resource Service Platform Function shell (list,n) { span = n/2 ; while (span ≧ 1) do { repeat f=0 ; / 表有無 SWAP 發生 / for i=1 to n-span do if list[i].key>list[i+span].key then { swap (list[i],list[i+span]) ; f=1 ; } until (f==0) / 此回合持續到無 SWAP 才停止 / span = span/2 ; } 31

Software Learning Resource Service Platform Shell Sort Ⅰ. Time complexity: 到目前為止, Best case 尚未定論,依 span 型 而定 Ⅱ. Space complexity: O(1) Ⅲ. Unstable [ 說明 ] 5 、 、 1 、 8 Pass 1. 1 、 、 5 、 8 → unstable span=2 Worst caseO( ) Avg. caseO( ) Best case O( ) 、 O( ) 、 O( ) 32

Software Learning Resource Service Platform Quick Sort 快速排序,又稱為 partition exchange sort ,就平均時間而 言,快速排序是所有排序中最佳的。 [ 作法 ] 33 Given: (R 0, R 1, R 2, R 3, ……….., R n-3, R n-2 R n-1 ) After first pass: R 1,..…, R S(i)-1, R 0, R S(i), R S(i)+1, …, R S(n-1) Pivot key i j two partitions

Software Learning Resource Service Platform Quick Sort R1R2R3R4R5R6R7R8R9R

Software Learning Resource Service Platform void procedure QuickSort(list, m, n) if (m<n) then i=m, j=n+1, p.k.=list[m].key Repeat repeat i=i+1 until list[i].key ≥p.k. repeat j=j-1 until list[i].key ≤p.k. if (i<j) then swap(list[i], list[j]) Until i ≥ j swap(list[m], list[j]) QuickSort(list, m, j-1) QuickSort(list, j+1, n) End ; {of if} End ; {of Qsort} 35

Software Learning Resource Service Platform Quick Sort Ⅰ. Time complexity: Best case: P.K 正確位置將 data 串列切割成二等分 T(n)= c*n + 2T( ) = 4*T ( )+2cn = n*T ( )+ = n+ cnlogn = O(nlogn) 36

Software Learning Resource Service Platform Quick Sort Worst case: 資料剛好是由小到大或由大到小,所以選到的 key 不是最大就是最小 T(n) ≦ cn + T(n-1) ≦ cn + T( cn + T(n-2)) ≦ 2cn + T(n-2) ≦ 3cn + T(n-3). ≦ (n-1)cn + T(1) = O( ) 37

Software Learning Resource Service Platform Quick Sort Average case 下, Time complexity 為 O(nlogn) Ⅱ. 快速排序是不穩定的排序 (unstable) Ⅲ. Space complexity: O(logn)~O(n) 在額外的需求方面,需要有一些空間當作堆疊來 完成遞迴 的特性,而 stack 的 size 取決於呼叫之深度。 38

Software Learning Resource Service Platform Merge Sort 觀念 : It merges the sorted lists(list[i],…,list[m]) and (list[m+1],…,list[n]), into a single sorted list,(sorted[i],…,sorted[n]). Merge sort 可分為 :  Iterative  Recursive 39

Software Learning Resource Service Platform Iterative 作法 : 原來的檔案視為 n 個已排序且長度為 1 的檔案,把兩兩合併成 個 長度為 2 的檔案 ( 若 n 為奇數,那有一檔案之長度為 1) 。之後, 個 檔案在兩兩合併直到只剩下一個檔案為止。 e.g. 輸入檔案為 26 、 5 、 77 、 1 、 61 、 11 、 59 、 15 、 48 、 19 [26] [5] [77] [1] [61] [11] [59] [15] [48] [19] [ 5 、 26 ] [ 1 、 77 ] [ 11 、 61 ] [ 15 、 59 ] [19 、 48 ] [ 1 、 5 、 26 、 77 ] [11 、 15 、 59 、 61] [19 、 48] [1 、 5 、 11 、 15 、 19 、 26 、 48 、 59 、 61 、 77] 40

Software Learning Resource Service Platform Iterative Ⅰ. Time complexity: Best , Worst , Average case 為 O(nlogn) Ⅱ. 是 stable 的 sorting method Ⅲ. 需要 O(n) 之額外空間 41

Software Learning Resource Service Platform Recursive  採用〝 Divide and Conquer 〞  作法 : (1)data 串列一律切割成兩等分 (2) 左、右半部子串列各自進行 merge sort (3) 合併左、右半部成一個檔案 42

Software Learning Resource Service Platform 26 、 5 、 77 、 1 、 61 、 11 、 59 、 15 、 48 、 19 [5 、 26] [77] [1 、 61] [11 、 59] [15] [19 、 48] [5 、 26 、 77] [1 、 61] [11 、 15 、 59] [19 、 48] [1 、 5 、 26 、 61 、 77] [11 、 15 、 19 、 48 、 59] [1 、 5 、 11 、 15 、 19 、 26 、 48 、 59 、 61 、 77] 43

Software Learning Resource Service Platform Procedure rMergeSort (Var x:afile ; l, u:Integer ; Var p:Integer ) Begin If l ≧ u Then p:=l else Begin mid := (1+u) div 2 ; rMergeSort(x,l,mid,q) ; / 左半 rMergeSort(x,mid+1,u,r) ; / 右半 ListMerge(x,q,r,p) ; / 合併 q , r 兩個 run 成一個 run End ; {of if} End ; {of rMergeSort} 44

Software Learning Resource Service Platform Heap Sort 作法 : Heap sort begins by building a heap out of the data set, and then removing the largest item and placing it at the end of the partially sorted array. After removing the largest item, it reconstructs the heap, removes the largest remaining item, and places it in the next open position from the end of the partially sorted array. This is repeated until there are no items left in the heap and the sorted array is full. 45

Software Learning Resource Service Platform 、 21 、 37 、 15 、 52 、 15+ 、 5 、 40 ,則 Heap sort 過程 : Heap Sort

Software Learning Resource Service Platform 輸出 52 輸出 40 47

Software Learning Resource Service Platform 輸出 37 輸出 35 48

Software Learning Resource Service Platform 輸出 21 輸出 15 49

Software Learning Resource Service Platform 輸出 15+ 輸出 5 50

Software Learning Resource Service Platform Heap Sort Ⅰ. Time complexity: Best , Average , Worst case 均為 O(nlogn) [ 說明 ] 1. 建立 heap: O(n) → bottom up 法 2. 執行 n-1 回合,每回合花 O(logn) 時間執行〝 Delete Max 〞 動作∴花了 O(nlogn) ,因此總共時間計算 O(n+nlogn)= O(nlogn) Ⅱ. Unstable method Ⅲ. Space complexity: O(1) 51

Software Learning Resource Service Platform Radix Sort  LSD radix sort (1) 假設 r 為使用之基底,需要準備 r 個 buckets (2) 若有 m 位數字 ( 不是 m 個 ) 則 LSD 需要 m 次的過程 52

Software Learning Resource Service Platform 179 、 208 、 306 、 93 、 859 、 984 、 55 、 9 、 271 、 33 作 Radix sort Pass 1. ( 個位數 ) 合併 :271 、 93 、 33 、 984 、 55 、 306 、 208 、 179 、 859 、

Software Learning Resource Service Platform Pass 2. ( 十位數 ) 合併 :306 、 208 、 9 、 33 、 55 、 859 、 271 、 179 、 984 、 93 Pass 3. ( 百位數 ) 合併 :9 、 33 、 55 、 93 、 179 、 208 、 271 、 306 、 859 、

Software Learning Resource Service Platform Radix Sort Ⅰ. Time complexity : d 為最大鍵值位數個數, n=data 數, r = base Ⅱ. Space complexity : → 額外空間需求來自於〝 Bucket size 〞 = r 個 bucket*n Ⅲ. Stable 55

Software Learning Resource Service Platform Summary NameBest timeWorst timeAvg.timespaceStability InsertionO(n)O(1)Y SelectionO(1)N BubbleO(n)O(1)Y ShellO(1)N QuickO(nlogn) O(logn)~O(n)N MergeO(nlogn) O(n)Y HeapO(nlogn) O(1)N 56

Software Learning Resource Service Platform Summary 資料量少且資料已排序過, Insertion sort 是最佳的 在平均情況下 (average case) , Quick sort 是最佳的 在最壞情況下 (worst case) , Merge sort 是最佳的, heap sort 是次佳的 57

Software Learning Resource Service Platform Ans: (1) 為一個 complete binary tree ,可分為 min-heap 及 max- heap 以 max-heap 為例,需要滿足 : 1. 所有子點的鍵值均小於父點鍵值 2.Root 為所有 node 中,具有最大鍵值 58 Question:

Software Learning Resource Service Platform (2) 以建 max-heap 為例 :

Software Learning Resource Service Platform

Software Learning Resource Service Platform

Software Learning Resource Service Platform 62 Reference  Ellis Horowitz, Sartaj Sahni, and Susan Anderson-Freed 〝 Fundamentals of Data Structures in C 〞, W. H. Freeman & Co Ltd,  Ellis Horowitz, Sartaj Sahni, and Dinesh Mehta 〝 Fundamentals of Data Structures in C++ 〞 Silicon Pr, 2006  Richard F.Gilberg, Behrouz A. Forouzan, 〝 Data Structures: A Pseudocode Approach with C 〞, S Baker & Taylor Books, 2004  Fred Buckley, and Marty Lewinter 〝 A Friendly Introduction to Graph Theory 〞 Prentice Hall, 2002  〝資料結構 - 使用 C 語言〞蘇維雅譯,松崗, 2004  〝資料結構 - 使用 C 語言〞 蔡明志編著,全華, 2004  〝資料結構 ( 含精選試題 ) 〞洪逸編著,鼎茂, 2005