heap data structure question..

This is a discussion on heap data structure question.. within the C Programming forums, part of the General Programming Boards category; there is T a binary tree, for each z node (not a leaf) we define NPL(z) (null path length) as ...

  1. #1
    Registered User
    Join Date
    Nov 2011
    Posts
    26

    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
    key[parent[z]]<=key[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]]
    and
    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
    Location
    Long Beach, CA
    Posts
    5,459
    Duplicated here: merging two heaps in psedo code.

    Mods, please lock/close.

  3. #3
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,485
    Agreed.
    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.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

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, 12:47 PM
  4. data structure question
    By miami_victor in forum C++ Programming
    Replies: 13
    Last Post: 12-30-2004, 11:56 PM
  5. Data structure question.
    By ronenk in forum C Programming
    Replies: 9
    Last Post: 10-03-2004, 10:58 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21