public static void CreateMaxHeap(int[] a)
{
for (int heapsize = 0; heapsize < a.Length; heapsize++)
{
int n, p;
n = heapsize;
while (n > 0)
{
p = (n - 1) / 2;
if(a[n]>a[p])
Swap(a,n,p);
n = p;
}
}
} // end of create heap
views:
380answers:
2
+4
A:
it's O(nlgn)
you iterate through the entire array that takes O(n). but every iteration you go back through the array by dividing by 2 repeatedly. so every iteration you're adding the lgn to it which is log base 2 of n.
as for making it better, the first thing i see is that when heapsize is zero, nothing happens. that's kindof wasteful of resources... so maybe start at 1. that's all.
Victor
2009-07-11 19:27:34
Cool...I got it....how can I make it better. This talks about http://en.wikipedia.org/wiki/Heapsort....here there is a bottom up approach which it says that it runs in O(n) time....but I am not able to understand how?
Learner
2009-07-11 19:36:35
you don't understand how it's O(n) or you don't understand how to implement it?
Victor
2009-07-11 19:45:48
@Learner - Where does it say that it's O(n)? The article mentions smoothsort, which is still O(nlgn), but gets close to O(n) if the input is somewhat sorted already.
Cypher2100
2009-07-11 19:58:11
thisThe heapify function can be thought of as building a heap from the bottom up, successively shifting downward to establish the heap property. An alternative version (shown below) that builds the heap top-down and shifts upward is conceptually simpler to grasp. This "siftUp" version can be visualized as starting with an empty heap and successively inserting elements. However, it is asymptotically slower: the "siftDown" version is O(n), and the "siftUp" version is O(n log n) in the worst case. The heapsort algorithm is O(n log n) overall using either version of heapify. is what article says
Learner
2009-07-11 20:01:37
victor: I understand how it is implemented, what I don't understand it how is it O(n), the siftDown function....
Learner
2009-07-11 20:02:40
The O(n) relays on the fact that the you are doing O(n) actions, but not all of them are ln(n) some are shorter actions, if you do the math, it can be proven to be O(n). There's a prove on http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262032937
Liran Orevi
2009-07-11 20:11:27
The whole O(n) thing comes from initially creating a heap before sorting, not the sorting itself. Here's the proof that the heapify method is O(n) http://en.wikipedia.org/wiki/Binary_heap#Building_a_heap
Cypher2100
2009-07-11 21:18:14
A:
design an algorthim for cheaking whether an array A[1......n] of integers is binary heap or not and determine its time efficiency.
zainab
2010-05-28 10:31:54