# Cutting a heap at a given node

• 07-19-2007
kris.c
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?
• 07-19-2007
St0rM-MaN
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"
• 07-19-2007
brewbuck
Quote:

Originally Posted by kris.c
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.
• 07-19-2007
brewbuck
Quote:

Originally Posted by St0rM-MaN
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.
• 07-19-2007
@nthony
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).
• 07-20-2007
kris.c
@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?
• 07-20-2007
brewbuck
Quote:

Originally Posted by kris.c
3. Now. call heapify on the new modified array.

Not necessary. After sliding everything to the left, the result is already a heap.

Quote:

>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.
• 07-20-2007
brewbuck
Quote:

Originally Posted by @nthony
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.
• 07-20-2007
kris.c
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.
• 07-20-2007
kris.c
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.
• 07-21-2007
MacNilly
Quote:

Originally Posted by kris.c
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?
• 07-21-2007
MacNilly
Quote:

Originally Posted by kris.c
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?
• 07-21-2007
kris.c
>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.
• 07-21-2007
MacNilly
Quote:

Originally Posted by kris.c
>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?

Quote:

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.