Heaps Basic ldea Heaps:basic operations TheMAX-HEAPIFY procedure,which runs in O(lg n)time,is the key to main- faining the max-heap property. The BUILD-MAX-HEAPprocedure,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的，。左，生，2 0Q0
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(lg n)time,is the key to main- taining the max-heap property. The BUILD-MAX-HEAPprocedure,which runs in linear time,produces a max- heap from an unordered input array. TheHEAPSORT procedure,which runs in O(nIgn)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的，，左+生 0Q0
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(lg n)time,is the key to main- aining the max-heap property. The BUILD-MAX-HEAPprocedure,which runs in linear time,produces a max- heap from an unordered input array. TheHEAPSORT procedure,which runs in O(nIgn)time,sorts an array in place. The MAX-HEAP-INSERT HEAP-EXTRACT-MAX HEAP-INCREASE-KEY, and HEAP-MAXIMUM procedures,which run in O(Ign)time,allow the heap data structure to implement a priority queue. 4口4的，，左·生，生 0Q0
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 rocedure,which runs in O(lg n)time,is the key to main- aining the max-heap property. The BUILD-MAX-HEAPprocedure,which runs in linear time,produces a max- heap from an unordered input array. The HEAPSORT procedure,which(runs in o(nlgn)time,sorts an array in place. The MAX-HEAP-INSERT HEAP-EXTRACT-MAX HEAP-INCREASE-KEY, and HEAP-MAXIMUM procedures,which run in O(Ign)time,allow the heap data structure to implement a priority queue. 4口4的，，左·生，生
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 rocedure,which runs in O(Ig n)time,is the key to main- aining the max-heap property. TheBUILD-MAX-HEAPprocedure,which runs in linear time,produces a max- heap from an unordered input array. The HEAPSORT procedure,which(runs in O(nIgn)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 priority queue. 發 口4心，左·急，空 0Q0 MA Jun (Institute of Computer Software) Problem Solving May4.2022 6/30
Heaps Basic Idea Heaps: basic operations MA Jun (Institute of Computer Software) Problem Solving May 4, 2022 6 / 30