Cutting a heap at a given node

This is a discussion on Cutting a heap at a given node within the C Programming forums, part of the General Programming Boards category; On cutting a heap at some internal node, we get two parts, one is a heap by itself. But, how ...

  1. #1
    Eager young mind
    Join Date
    Jun 2006
    Posts
    342

    Cutting a heap at a given node

    On cutting a heap at some internal node, we get two parts, one is a heap by itself. But, how can we "heapify" the other part? Assuming that the heap has been implemented by using arrays, is it possible to pull of something like this without using another array to copy the elements and then "heapify"-ing that array?
    In the middle of difficulty, lies opportunity

  2. #2
    life is a nightmare
    Join Date
    Apr 2007
    Posts
    127
    i didn't get a word of that ?

    what are you trying to do ?

    and heap is a part of memory to store dynamically allocated memory i don't think you can implement it using a "fixed size array"

  3. #3
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,249
    Quote Originally Posted by kris.c View Post
    On cutting a heap at some internal node, we get two parts, one is a heap by itself. But, how can we "heapify" the other part? Assuming that the heap has been implemented by using arrays, is it possible to pull of something like this without using another array to copy the elements and then "heapify"-ing that array?
    Imagine the following heap:

    Code:
            1
          5   3
         8 6 4 7
    Written as an array:

    1 5 3 8 6 4 7

    Suppose you want to remove the 5/8/6 subtree. Strike these elements out of the array:

    1 x 3 x x 4 7

    Compact the array by sliding everything to fill the x's:

    1 3 4 7

    Rewrite as a heap:

    Code:
          1
        3   4
      7
    Proof is left as an exercise to the reader.

    The striking and shifting can be done concurrently, instead of as two stages.

  4. #4
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,249
    Quote Originally Posted by St0rM-MaN View Post
    and heap is a part of memory to store dynamically allocated memory i don't think you can implement it using a "fixed size array"
    In CS, "heap" means two things. The first is the area of memory where dynamic allocation happens (what you're thinking of). The other meaning is a tree-like data structure with the property that some ordering relation holds between all parents and their children (such as, each child is always greater than its parent, for instance).

    If we require that the heap be compact, we can represent it using an array instead of an actual tree structure. This allows for efficient manipulations on the heap using indexing instead of traversal.

  5. #5
    Registered Abuser
    Join Date
    Jun 2006
    Location
    Toronto
    Posts
    591
    I'm wondering if those two concepts are not entirely unrelated... Much like how a program's "stack" is based of the stack data structure, the term "heap" seems too coincidental not to have similar origins. Although I'm certain modern OSs don't just use simple heaping algorithms to keep track of free blocks (wiki says they may use trees, which is actually heap-ish after-all), somehow I believe the usage of the term must have originated from such an implementation at some point in time. Can anyone clear up the origins of the term "the heap"? (sorry for the side track, just a burning question).

  6. #6
    Eager young mind
    Join Date
    Jun 2006
    Posts
    342
    @BREWBUCK:
    After reading your post, I thought we could do something like this:
    1. Since i know the starting index of the sub-heap, I can recursively change the values (of the elements in the sub heap) in the main array, to something like -999. At the same time, also copy these values into another array as we need two heaps in the end.
    2. Now, traverse the array and perform the sliding as u said, that should not be very difficult.
    3. Now. call heapify on the new modified array.

    >The striking and shifting can be done concurrently, instead of as two stages.
    Could u explain how that can be done?
    In the middle of difficulty, lies opportunity

  7. #7
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,249
    Quote Originally Posted by kris.c View Post
    3. Now. call heapify on the new modified array.
    Not necessary. After sliding everything to the left, the result is already a heap.

    >The striking and shifting can be done concurrently, instead of as two stages.
    Could u explain how that can be done?
    I don't want to give it all away :-) Just think about the relationship between the index of a struck-out element, and the element that will ultimately fill its place. It helps to write out a simple example heap like the one I gave.

  8. #8
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,249
    Quote Originally Posted by @nthony View Post
    I'm wondering if those two concepts are not entirely unrelated...
    I can't think of any way a heap data structure would be helpful in a memory allocator. I suppose if you wanted to assign blocks based on some priority associated with each block, the blocks might be kept in a heap to help prioritize the allocations. But I know of no general-purpose allocator that does something like that. Of course, anything and everything can be imagined, and has probably been done somewhere.

    I think the term "heap" in the context of allocation is based on the verb usage of the word -- to heap things into a pile. A "stack" is a very organized data structure -- modifications only ever occur at the top of the stack. When you imagine a heap, you presumably imagine a more disorderly collection of items. And that's basically what the dynamic memory space is -- a place where all assorted and sundry allocations occur.

  9. #9
    Eager young mind
    Join Date
    Jun 2006
    Posts
    342
    Well, as far as the relationship is concerned, if I am striking out an element, I am going to slide in its sibling. If thats what you are implying.
    In the middle of difficulty, lies opportunity

  10. #10
    Eager young mind
    Join Date
    Jun 2006
    Posts
    342
    I am still not very sure about it. In doing both the operations at the same time, we are actually messing with the array indices. Its now harder to keep track of the nodes that belong to the sub-heap that is to be deleted.
    In the middle of difficulty, lies opportunity

  11. #11
    Registered User MacNilly's Avatar
    Join Date
    Oct 2005
    Posts
    324
    Quote Originally Posted by kris.c View Post
    I am still not very sure about it. In doing both the operations at the same time, we are actually messing with the array indices. Its now harder to keep track of the nodes that belong to the sub-heap that is to be deleted.
    I am just curious, why do you want to delete a node (or subtree) from a heap?

  12. #12
    Registered User MacNilly's Avatar
    Join Date
    Oct 2005
    Posts
    324
    Quote Originally Posted by kris.c View Post
    I am still not very sure about it. In doing both the operations at the same time, we are actually messing with the array indices. Its now harder to keep track of the nodes that belong to the sub-heap that is to be deleted.
    I am just curious, why do you want to delete a node from a heap?

    In all practicality, you could run standard BinaryTree_Delete function on a key value. Right after, run a ReHeap/Up/Down() algorithm that will fix your heap. In this way you avoid too much detail such as shifting specific elements in an array as suggested above.

    If you want to COPY an entire subtree of a heap(which is what I think you want to do), and also DELETE it from the original tree at the same time...

    run a post-order recursive deletion which, before
    freeing each node, copys it into a new tree?
    Last edited by MacNilly; 07-21-2007 at 01:37 AM.

  13. #13
    Eager young mind
    Join Date
    Jun 2006
    Posts
    342
    >I am just curious, why do you want to delete a node (or subtree) from a heap?
    A possible interview question.

    >ReHeap/Up/Down() algorithm
    I think the nomenclature is a bit different. Which algorithm are you talking about here?

    >run a post-order recursive deletion which, before
    freeing each node, copys it into a new tree?

    A heap is a binary tree which is filled completely at each level from the left to the right. On doing so, the heap property is not maintained.
    In the middle of difficulty, lies opportunity

  14. #14
    Registered User MacNilly's Avatar
    Join Date
    Oct 2005
    Posts
    324
    Quote Originally Posted by kris.c View Post
    >ReHeap/Up/Down() algorithm
    I think the nomenclature is a bit different. Which algorithm are you talking about here?
    The algorithm that maintains the heap property that array[n] <= array[2n+1] and array[n] <= array[2n + 2] (for a min heap). Reheap up is called when inserting elements and down is called when removing.

    >run a post-order recursive deletion which, before
    freeing each node, copys it into a new tree?

    A heap is a binary tree which is filled completely at each level from the left to the right. On doing so, the heap property is not maintained.
    No. That's called a full and complete binary tree. This is a heap.
    Last edited by MacNilly; 07-21-2007 at 09:23 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help Debugging my AVL tree program.
    By Nextstopearth in forum C Programming
    Replies: 2
    Last Post: 04-04-2009, 01:48 AM
  2. Unknown memory leak with linked lists...
    By RaDeuX in forum C Programming
    Replies: 6
    Last Post: 12-07-2008, 03:09 AM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  5. Contest Results - May 27, 2002
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 06-18-2002, 01:27 PM

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