南京大学：《计算机问题求解》课程教学资源（课件讲稿）Heap & HeapSort ?

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

Problem Solving 2-11 Heap & Heapsort MA Jun Institute of Computer Software May 4, 2022

Contents ①Heaps ② Heapsort ③Priority Queue 4口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 ldea Heap 發 口+4y，。法，4生。2Q0 MA Jun (Institute of Computer Software) Problem Solving May4.2022 1/30

Heaps Basic Idea Heap MA Jun (Institute of Computer Software) Problem Solving May 4, 2022 1 / 30

Heaps Basic ldea Heaps The(binary)heap data structure is an array object that we can view as a nearly complete binary tree 發 4口4的在是安QC MA Jun (Institute of Computer Software) Problem Solving May4.2022 2/30

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 4, 2022 2 / 30

Heaps Basic ldea 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 14 10 (a) 發 4口4的在是安QC MA Jun (Institute of Computer Software) Problem Solving May4.2022 2/30

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 4, 2022 2 / 30

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(i)】≤A[间 酸 口卡4的左生，登 0a0 MA Jun (Institute of Computer Software) Problem Solving May4.2022 3/30

Heaps Basic Idea Heaps: Max-heap VS Min-heap 12 10 9 5 6 1 Max-heap property A [P arent(i)] ≥ A [i] 1 5 9 10 6 12 Min-heap property A [P arent(i)] ≤ A [i] MA Jun (Institute of Computer Software) Problem Solving May 4, 2022 3 / 30

Heaps Basic ldea Heaps:Storage Q 1:Why do we implement a heap with an array? 16 14 10 12345678910 1614i0879324 (b) 發 口+4的，▣老4=2)QC MA Jun (Institute of Computer Software) Problem Solving May4.2022 4/30

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 4, 2022 4 / 30

Heaps Basic ldea Heaps:Storage Q 1:Why do we implement a heap with an array? PARENT() 16 1 return [i/2] 10 12345678910 LEFT(i) 1614i0879324] 1 return 2i RIGHT(i) (b) 1 return 2i+1 Easy to index 4口4的，，左+生，2分Q0 MA Jun (Institute of Computer Software) Problem Solving May4.2022 4/30

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 4, 2022 4 / 30

Heaps Basic ldea Heaps:Storage Q 1:Why do we implement a heap with an array? PARENT() 16 1 return [i/2] 10 12345678910 LEFT(i) 1614i0879324] 1 return 2i RIGHT(i) (b) 1 return 2i+1 Easy to index ●Save memory 4口4的，，左+生，2分Q0 MA Jun (Institute of Computer Software) Problem Solving May4.2022 4/30

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 4, 2022 4 / 30