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 o Save memory o Better cache locality 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:Height The height of a node o The number of edges on the longest simple downward path from the node to a leaf. 發 口+4的，法=2QC MA Jun (Institute of Computer Software) Problem Solving May4.2022 5/30
Heaps Basic Idea Heaps: Height The height of a node The number of edges on the longest simple downward path from the node to a leaf. The height of a heap The height of its root, Θ(lg n). A heap of n elements is based on a nearly complete binary tree h=3 h=2 h=1 h=1 h=0 h=0 MA Jun (Institute of Computer Software) Problem Solving May 4, 2022 5 / 30
Heaps Basic ldea Heaps:Height The height of a node o The number of edges on the longest simple downward path from the node to a leaf. The height of a heap The height of its root,(lgn). o A heap of n elements is based on a nearly complete binary tree 16h=3 h=2 14 1oh=1 h=1(8 3h=0 h=0 (a) MA Jun (Institute of Computer Software) Problem Solving May4.2022 5/30
Heaps Basic Idea Heaps: Height The height of a node The number of edges on the longest simple downward path from the node to a leaf. The height of a heap The height of its root, Θ(lg n). A heap of n elements is based on a nearly complete binary tree h=3 h=2 h=1 h=1 h=0 h=0 MA Jun (Institute of Computer Software) Problem Solving May 4, 2022 5 / 30
Heaps Basic ldea Heaps:basic operations The MAX-HEAPIFY procedure,which runs in O(lg n)time,is the key to main- taining the max-heap property. The BUILD-MAX-HEAP procedure,which runs in linear time,produces a max- heap from an unordered input array. The HEAPSORT procedure,which runs in O(n Ign)time,sorts an array in place. The MAX-HEAP-INSERT,HEAP-EXTRACT-MAX,HEAP-INCREASE-KEY, and HEAP-MAXIMUM procedures,which run in O(Ig n)time,allow the heap data structure to implement a priority queue. 4口4的，，左+生，2Q0
Heaps Basic Idea Heaps: basic operations MA Jun (Institute of Computer Software) Problem Solving May 4, 2022 6 / 30
Heaps Basic ldea Heaps:basic operations TheMAX-HEAPIFY procedure,which runs in O(lgn)time,is the key to main- taining the max-heap property. The BUILD-MAX-HEAP procedure,which runs in linear time,produces a max- heap from an unordered input array. The HEAPSORT procedure,which runs in O(n Ign)time,sorts an array in place. The MAX-HEAP-INSERT,HEAP-EXTRACT-MAX,HEAP-INCREASE-KEY, and HEAP-MAXIMUM procedures,which run in O(Ig n)time,allow the heap data structure to implement a priority queue. ，口+4的，。左，，生QG
Heaps Basic Idea Heaps: basic operations MA Jun (Institute of Computer Software) Problem Solving May 4, 2022 6 / 30