Lecture Note
University
University of California San DiegoCourse
CSE 100/101 | Data Structures and AlgorithmsPages
2
Academic year
2023
anon
Views
16
Improving the Analysis of the BuildHeap Procedure: A MoreAccurate Approach Because the BuildHeap process consists of around n/2 calls to the SiftDown operation, which has a running time of log n, it is sometimes assumedthat its execution time is O(n log n). This estimate, nevertheless, might beoverly pessimistic. The BuildHeap technique will be further examined and its running time will be more precisely estimated in this article. To do this, we will take intoaccount the fact that if the SiftDown process is invoked for a node near theleaves, sifting it down will take considerably less time than log n. For the reasonthat it cannot make more swaps than the height of the relevant subtree before itreaches the leaves. In addition, there are a lot of nodes close to the root in a heap. The root is the only node with a height of log n, followed by two nodes with log n - 1, fournodes with log n - 2, and so on, with around n/4 nodes having a height of just 1. Let's estimate the BuildHeap procedure's duration more precisely in light of this. Analyzing the Cost of Sifting Down Let's examine a schematic illustration of a heap to help with this. There is just one node at the top level, and sifting it down incurs a logarithmic cost.There are at most n/2 nodes on the final level, and there is only room for oneswap after they are culled. There are at most n/4 nodes on the following level,and there are a maximum of two swaps required to sift them down. We can get the entire running time of the BuildHeap operation by adding up all of these charges. Let's set an upper limit on this sum equal to a similarsum to make it more manageable. The sum is , where the index of the sum, I can 1/2 + 2/4 + 3/8 + 4/16 + 5/32 +... have a maximum value of log n.
The sum from I = 1 to infinity of I divided by 2i can serve as the upperboundary of this sum. Although this total is finite in the instance of theBuildHeap procedure's running time, we shall upper-bound it by the infinitesum to simplify the analysis. Estimating the Running Time We will demonstrate that the sum is equal to two. This indicates that the BuildHeap procedure takes O(n + n log n) = O to complete (n log n). This is aconsiderably more accurate estimation of the BuildHeap procedure's runningtime than the O estimate that was previously employed (n log n). So by considering the various heap properties as well as the cost of filtering down for nodes at various heights, we have been able to produce amore accurate estimation of the BuildHeap function's execution time.
Analysis of the BuildHeap Procedure
Please or to post comments