Heaps Basic Idea Heaps:basic operations THeMAX-HEAPIFY procedure,which runs in O(Ig 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(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步，，左·生，空 0a0
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Heaps Basic Idea Heaps: basic operations MA Jun (Institute of Computer Software) Problem Solving May 7, 2020 6 / 29
Heaps Basic Idea Heaps:basic operations THeMAX-HEAPIFY procedure,which runs in O(Ig 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(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(Ign)time,allow the heap data structure to implement a priority queue. 4口4步，，左·生，生 0a0
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Heaps Basic Idea Heaps: basic operations MA Jun (Institute of Computer Software) Problem Solving May 7, 2020 6 / 29
Heaps Basic Idea Heaps:basic operations THeMAX-HEAPIFY procedure,which runs in O(Ig 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. TheHEAPSORT 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步，，左·生，空 0a0
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Heaps Basic Idea Heaps: basic operations MA Jun (Institute of Computer Software) Problem Solving May 7, 2020 6 / 29
Heaps Basic Idea 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(nlg n)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步，，左·生，发 0a0
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Heaps Basic Idea Heaps: basic operations MA Jun (Institute of Computer Software) Problem Solving May 7, 2020 6 / 29
Heaps Basic Idea Heaps:basic operations THeMAX-HEAPIFY rocedure,which runs in O(lg 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(nlg n)time,sorts an array in place. The MAX-HEAP-INSERT HEAP-EXTRACT-MAX HEAP-INCREASE-KEY, and HEAP-MAXIMUM procedures,which run in O(lg n)time,allow the heap data structure to implement a priority queue. 口卡+①，2生QC MA Jun (Institute of Computer Software) Problem Solving May7,20206/29
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Heaps Basic Idea Heaps: basic operations MA Jun (Institute of Computer Software) Problem Solving May 7, 2020 6 / 29