Thread: heap data structure question..

  1. #1
    Registered User
    Join Date
    Nov 2011

    heap data structure question..

    there is T a binary tree, for each z node (not a leaf) we define
    NPL(z) (null path length) as the length of the shortest path from the node to the leaf.
    we add npl[z] to each node.
    binary tree T is called left tree if npl[left[z]]>=npl[right[z]]

    the left tree H is called left heap if for every node z
    k- represents the priority if the heap

    prove that if we build a binary heap as a binary tree (using pointers ,not arrays) then its left heap

    so we need to show that our binary tree is left
    by npl[left[z]]>=npl[right[z]]
    key[parent[z]]<=key[z] in our tree

    in my book a heap is represented by an array and we translate this array into a tree picture

    i dont know how to imagine this tree they want me to show about

  2. #2
    Registered User
    Join Date
    Nov 2010
    Long Beach, CA
    Duplicated here: merging two heaps in psedo code.

    Mods, please lock/close.

  3. #3
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    The edge of the known universe
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 15
    Last Post: 10-25-2011, 10:56 PM
  2. Abstract data structure question
    By Shadow20 in forum C Programming
    Replies: 17
    Last Post: 03-26-2011, 09:12 PM
  3. question about data structure
    By renaissance in forum C++ Programming
    Replies: 3
    Last Post: 02-17-2005, 01:47 PM
  4. data structure question
    By miami_victor in forum C++ Programming
    Replies: 13
    Last Post: 12-31-2004, 12:56 AM
  5. Data structure question.
    By ronenk in forum C Programming
    Replies: 9
    Last Post: 10-03-2004, 10:58 AM