COMP 352 Lecture 19: Heap, Bottom-Up Heap, Adaptable Priority Queue, Merge Sort, and Divide and Conquer Paradigm
16 Mar 2016
School
Department
Course
Professor
Document Summary
If you are given two heaps, you can merge it by creating a new heap with a root. Down heap is performed to restore heap order property. Is faster than with time complexity of o(n), which is lower than o(n logn) This speeds up the first phase of heap-sort. This can be done if height and # of leaf nodes are known (equations are in sub-headings) Each node is traversed by a maximum of two paths, the total number of nodes of proxy path is o(n) Heap =\= priority queue, a heap is an implementation of a pq. Height of heap (if all heaps are full) (cid:1866)= 2(cid:2868)+2(cid:2869)+2(cid:2870)+ +2(cid:3035) Traditional implementation priority cannot be changed; however, it can be changed in adaptable pq. Children are visited in an order from left to right (in case of binary) In other cases, the order will be depended on the implementation (children have an identity - e. g. 1 2 3 4)
