Results 1 to 8 of 8

Math Help - question on binary heaps

  1. #1
    Senior Member
    Joined
    Sep 2009
    Posts
    299

    Cool question on binary heaps

    When merging 2 binary heaps (implemented as arrays), the worst case running time is O(n).
    But I just want to figure out why its that.

    So to do this, you would merge the two arrays in one, then create an empty heap, then for each element in the new array, you insert that element in the heap.

    Now, to insert 1 element thats O(log(n)), but you do that n times, because once for each element. But then I'm getting O(n*log(n)). Why is this not right?
    Last edited by Sneaky; January 23rd 2013 at 07:57 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Bar0n janvdl's Avatar
    Joined
    Apr 2007
    From
    Meh
    Posts
    1,630
    Thanks
    6

    Re: question on binary heaps

    Quote Originally Posted by Sneaky View Post
    When merging 2 binary heaps (implemented as arrays), the worst case running time is O(n).
    But I just want to figure out why its that.

    So to do this, you would merge the two arrays in one, then create an empty heap, then for each element in the new array, you insert that element in the heap.

    Now, to insert thats O(log(n)), but you do that n times, because once for each element. But then I'm getting O(n*log(n)). Why is this not right?
    I'm curious, why do you say insertion of n elements has a running time of O(log(n)) ?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Sep 2009
    Posts
    299

    Re: question on binary heaps

    I mean, inserting 1 element is O(log(n)), so for inserting n elements, shouldn't it be O(n*log(n))?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Bar0n janvdl's Avatar
    Joined
    Apr 2007
    From
    Meh
    Posts
    1,630
    Thanks
    6

    Re: question on binary heaps

    Quote Originally Posted by Sneaky View Post
    I mean, inserting 1 element is O(log(n)), so for inserting n elements, shouldn't it be O(n*log(n))?
    Bear with me please, I'm also trying to wrap my head around this problem.

    Wouldn't you need to find the largest/smallest elements in the heap when merging or creating a new heap? That has a running time of O(n).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778

    Re: question on binary heaps

    Wikipedia says that inserting elements one by one indeed takes time O(n*log(n)) and is not the optimal way to create a heap. But "heapifying" any array of length n takes time O(n).
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Sep 2009
    Posts
    299

    Re: question on binary heaps

    Yeah the optimal way is O(n), so I am trying to understand how the algorithm goes.
    Suppose I have this array (the heap looks like in the picture). It currently is out of order and needs to be fixed. (into a max heap of type binary)
    Can anyone help explain how this can be fixed?

    Follow Math Help Forum on Facebook and Google+

  7. #7
    Bar0n janvdl's Avatar
    Joined
    Apr 2007
    From
    Meh
    Posts
    1,630
    Thanks
    6

    Re: question on binary heaps

    A psuedocode algorithm is available here: Binary heap - Wikipedia, the free encyclopedia (Just below the "Delete" section)

    EDIT:
    Actually, here is an explanation of why the optimal method is O(n):
    Binary heap - Wikipedia, the free encyclopedia
    Last edited by janvdl; January 24th 2013 at 09:26 PM.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member
    Joined
    Sep 2009
    Posts
    299

    Re: question on binary heaps

    ok I understand how the algorithm works now and I see it's worst case running time is O(n), but how do you obtain whats the omega is? I believe it is supposed to be omega(n) which makes it theta(n), but how do you get omega(n)?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Binary Tree Question
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 5th 2011, 07:40 PM
  2. Simple Binary Operations Question
    Posted in the Advanced Algebra Forum
    Replies: 7
    Last Post: September 21st 2011, 03:51 PM
  3. Binary question
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: November 28th 2010, 09:50 AM
  4. Question about Binary relations
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: September 13th 2009, 10:23 AM
  5. binary string probability question
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: June 1st 2008, 07:56 PM

Search Tags


/mathhelpforum @mathhelpforum