Heaps Priority Queues Complete The(binary)heap data structure is binary tree an array object hat can be viewed as a nearly complete binary tree 1234567 16141087932 14 Parent(=Li2」 3 All leaves Left(o 891 have the Right( 21+1 2④4① same depth All internal A max-heap: child<= parent nodes have 2 children A min-heap: child > parent CS3381 Des Anal of Alg(2001-2002 SemA) City Univ of HK /Dept of CS /Helena Wong http://www.cs.cityu.edu.hk/-helena 6. Graph Algorithms-3CS3381 Des & Anal of Alg (2001-2002 SemA) City Univ of HK / Dept of CS / Helena Wong http://www.cs.cityu.edu.hk/~helena 6. Graph Algorithms - 3 Heaps & Priority Queues The (binary) heap data structure is: • All leaves have the same depth • All internal nodes have 2 children Complete binary tree: 16 14 10 8 7 9 3 2 4 1 16 14 10 8 7 9 3 2 4 1 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 an array object that can be viewed as a nearly complete binary tree Parent(i) =  i/2  Left(i) = 2i Right(i) = 2i+1 A max-heap: child <= parent A min-heap: child >= parent