0 votes 0 votes What will be the recurrence relation for max heapify. Please explain with example. Algorithms algorithms recurrence-relation + – _Madhuri asked Nov 2, 2021 • retagged Jun 27, 2022 by makhdoom ghaya _Madhuri 329 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes @_Madhuri Heap is a Binary Search Tree (almost) and maintain few important properties to maintain the Heap order… ## Root has the largest element ### Since It is a Binary Search Tree - right subtree is also heap and left subtree is also a heap and maintain the heap property. #### Right subtree value and Left subtree value is less than or equal to the Root of the Heap. The main job of Max Heapify is to correct the heap order , meaning, if any subtree does not maintain the heap order, correct the order by shifting the nodes of heap. In this process the tree can get skewed which is the worst case for heap and worst case analysis for the max heapify algorithm... Total running time for Max Heapify is O(h) + c ... where h is height of tree and c is number of time you call Max Heapify. Also, Heap is a tree then , O(h) == O(log n), because h <= log n Now, the recurrence relation depict the same , that is , the effort to maximize the tree. T(n) = T(2n/3) + O(1).. 1. https://gateoverflow.in/43251/Recurrence-relation-heapify-function-heapsort-algorithm Awe111 answered Nov 2, 2021 Awe111 comment Share Follow See all 0 reply Please log in or register to add a comment.
