南京大学：《计算机问题求解》课程教学资源（课件讲稿）堆的结构、实现以及算法应用 Heap & HeapSort

Problem Solving 2-11 Heap Heapsort MA Jun Institute of Computer Software May7,2020 +口+4y，4三，4=，三0QC

Problem Solving 2-11 Heap & Heapsort MA Jun Institute of Computer Software May 7, 2020 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Contents ① Heaps ② Heapsort ③Priority Queue +口+4y，4三4兰，左0QC

Contents 1 Heaps 2 Heapsort 3 Priority Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Contents ① Heaps Heapsort ③Priority Queue 4口+4y，4三，4兰，左0QC

Contents 1 Heaps 2 Heapsort 3 Priority Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Heaps Basic Idea Heap 口+4y，。法4生。2)Q0 MA Jun (Institute of Computer Software) Problem Solving May7,20201/29

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Heaps Basic Idea Heap MA Jun (Institute of Computer Software) Problem Solving May 7, 2020 1 / 29

Heaps Basic Idea Heaps The(binary)heap data structure is an array object that we can view as a nearly complete binary tree 口卡+①，2是生QC MA Jun (Institute of Computer Software) Problem Solving May7.20202/29

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Heaps Basic Idea Heaps The (binary) heap data structure is an array object that we can view as a nearly complete binary tree The tree is completely filled on all levels except possibly the lowest MA Jun (Institute of Computer Software) Problem Solving May 7, 2020 2 / 29

Heaps Basic Idea Heaps The(binary)heap data structure is an array object that we can view as a nearly complete binary tree o The tree is completely filled on all levels except possibly the lowest 16 0 (a) 口卡+①，2生QC MA Jun (Institute of Computer Software) Problem Solving May7.20202/29

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Heaps Basic Idea Heaps The (binary) heap data structure is an array object that we can view as a nearly complete binary tree The tree is completely filled on all levels except possibly the lowest MA Jun (Institute of Computer Software) Problem Solving May 7, 2020 2 / 29

Heaps Basic Idea Heaps:Max-heap VS Min-heap 10 9 9 10 12 Max-heap property Min-heap property A[Parent(i)]≥A[) A[Parent(iI≤A[j 口+4①◆1左·生·2Q0 MA Jun (Institute of Computer Software) Problem Solving May7.20203/29

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Heaps Basic Idea Heaps: Max-heap VS Min-heap 12 10 9 5 6 1 Max-heap property A [Parent(i)] ≥ A [i] 1 5 9 10 6 12 Min-heap property A [Parent(i)] ≤ A [i] MA Jun (Institute of Computer Software) Problem Solving May 7, 2020 3 / 29

Heaps Basic Idea Heaps:Storage Q-1:Why do we implement a heap with an array? 16 10 122345678910 1614108793241] (a)】 (b) 口卡+①，2生Q0 MA Jun (Institute of Computer Software) Problem Solving May7.20204/29

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Heaps Basic Idea Heaps: Storage Q-1: Why do we implement a heap with an array? Easy to index Save memory Better cache locality MA Jun (Institute of Computer Software) Problem Solving May 7, 2020 4 / 29

Heaps Basic Idea Heaps:Storage Q-1:Why do we implement a heap with an array? PARENT(i) 16 I return [i/2] 0 122345678910 LEFT(i) 1614108793241] 1 return 2i RIGHT(i) (a】 (b) 1 return 2i+1 Easy to index 口卡4①怎至月QC MA Jun (Institute of Computer Software) Problem Solving May7.20204/29

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Heaps Basic Idea Heaps: Storage Q-1: Why do we implement a heap with an array? Easy to index Save memory Better cache locality MA Jun (Institute of Computer Software) Problem Solving May 7, 2020 4 / 29

Heaps Basic Idea Heaps:Storage Q-1:Why do we implement a heap with an array? PARENT(i) 16 I return [i/2] 0 122345678910 LEFT(i) 1614108793241] 1 return 2i RIGHT(i) (a】 (b) 1 return 2i+1 Easy to index ●Save memory 口卡4①怎至月QC MA Jun (Institute of Computer Software) Problem Solving May7.20204/29

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Heaps Basic Idea Heaps: Storage Q-1: Why do we implement a heap with an array? Easy to index Save memory Better cache locality MA Jun (Institute of Computer Software) Problem Solving May 7, 2020 4 / 29