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
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"
Imagine the following heap:Originally Posted by kris.c
Written as an array:Code:1 5 3 8 6 4 7
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:
Proof is left as an exercise to the reader.Code:1 3 4 7
The striking and shifting can be done concurrently, instead of as two stages.
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.
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).
@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
Not necessary. After sliding everything to the left, the result is already a heap.
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.>The striking and shifting can be done concurrently, instead of as two stages.
Could u explain how that can be done?
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.
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
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
I am just curious, why do you want to delete a node (or subtree) from a heap?
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.
>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
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?
No. That's called a full and complete binary tree. This is a heap.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.
Last edited by MacNilly; 07-21-2007 at 09:23 AM.
