heaps implementation

[4ET0pfjN]

Should I implement a heap as a linked list of left, right pointers or should I use arrays? I tend to think linked list is more natural and intuitive to use recursion.

[naraku9333]

When I wrote a memory manager a couple semesters back, I dynamically allocated an array (memory pool) of adequate size. And used a couple arrays of lists to track allocated and free memory blocks

[4ET0pfjN]

so arrays it is, but does it hurt (in terms of efficiency) to use linked lists, since BST use linked lists with left and right pointers. That sounds like a cool project btw

[naraku9333]

Do you mean using a linked list for the memory pool? I'm sure you could, but I dont think it would be too efficient, at least not for the pool creation. LL are probably most useful IMO because of fast inserts at any location, which you shouldn't need (at least nothing jumps to mind) for a memory pool.

[4ET0pfjN]

I'm a little confused, why is that when it's deleting a node (from a heap), sources I checked online all talk about removing the root node w/ the deepest level, most leftward node. Why don't they choose to delete a node in the middle? I'm tired when I wrote this...I hope I make sense.

Here's Wikipedia:http://en.wikipedia.org/wiki/Binary_heap#Delete

And also, why do they choose to insert into an empty heap starting @ index 1, b/c it is also fine starting at index 0: the slight differences on how to find the parent, left and right children for a given node at index i:

from (staring at index 1 to insert node in an empty heap)
parent(i) = i/2
left(i) = 2*i
right(i) = 2*i + 1

to (starting at index 0 to insert node in an empty heap)
parent(i) = (i - 1)/2
left(i) = 2*i + 1
right(i) = 2*i + 2

Is it just convention to start @ indx 1 for heaps?

[kbw]

A heap takes large blocks of memory from a system allocator (or is provided with a block to work from) and sub allocates that memory. You have to handle requests for allocations of differing sizes and blocks to free.

The actual data structures you use depends on the implementation you choose. How do you intend to manage the blocks that are allocated/returned? Do you have to minimise fragmentation or do you just provide a basic implementation?

[ne555]

I think the OP is talking about max/min heaps, to implement priority queues.
Using arrays make sense because every level is full (except the last). New `nodes' would be added as in a push_back.

Using list, you will need to maintain the links. 3 links per node is a lot with basic types.
In terms of speed, they differ in the constant.


Don't know about the index convention.

[4ET0pfjN]

Just to be clear, as in ne555's reply, I am talking about building a heap, specifically min-heap.

Here is my question again:

I'm a little confused, why is that when it's deleting a node (from a heap), sources I checked online all talk about removing the root node w/ the deepest level, most leftward node. Why don't they choose to delete a node in the middle? I'm tired when I wrote this...I hope I make sense.

Here's Wikipedia:http://en.wikipedia.org/wiki/Binary_heap#Delete

[zb0S216C]

mx760 wrote:

"but does it hurt (in terms of efficiency) to use linked lists"

Linked-list are inefficient, because:

- Excessive calls to new will cause memory fragmentation
- Excessive calls to new impacts performance significantly during run-time
- Multiple calls to new can increase the chance of an exception, and handling exceptions can be expensive
- Data that isn't aligned contiguously (like an array) doesn't make effective use of the code/CPU cache

_Wazzak

[ne555]

You want a priority queue. If you implement it using a heap then the max/min element is at the root.
That's why you are interesting in deleting the root node.