Linked list implementation of Binary Min Heap (Having trouble with manipulation...)

Question

So i'm trying to implement a binary min heap. I understand what the binary min heap entails in terms of it's structure and it's properties. However I'm hitting a wall when I'm trying to implement it using pointers and nodes.

Im using a Node, which has right/left and pointers, int element and parent pointer. I also have a LastNode in place which points to the last node inserted.

My quarrel is I dont know what to do when I insert an element, in terms of the last Node. Here is what I mean.

Step 1.) Assume Heap is empty, so you create a root namely x where x contains the element and you set root.left/right = null and LastNode = root.left.

  X
 / \
0   0

This is the part where I'm stuck. I know when you create another node to store another element it will go in the left of X or where LastNode points to. My questions what do I do next with LastNode, do I point it to x.right ? I'm trying to keep insert(int x) running in logN, and The lastNode manipulation will get longer and more extensive at each level.

Can someone break it down? Thanks

Joiejoin

if this isn't homework, then there's a much simpler implementation for binary heaps: simply with an array – Patellate

If a Node has left, right, and parent pointers, it's not a LinkedList, it's a Tree. – Raimund

Yes, it's much easier using array, but it is homework. – Joiejoin

Answer 1

Well you need to insert the element on the last level of the heap and then from there figure out if you need to bubble up. So you need the lastNode pointer to indicate not the last element inserted (it could very well be the last one insterted, but it might have went all the way up being now the root; that's not helpful at all), but rather the parent of where you will insert this new element. Does that help?

(Later edit): There is a more optimal way of building the heap, but I feel that's not what you need right now, so that's why I assumed you'll be using the simple insertion with is O(log n) for every new element.

Sulk

I understand what you're saying. However, how do I account for lastNode's (whatever it points to) Parent.right node? Can you give an example, building it from scratch or something. – Joiejoin

Spot on! That's exactly the problem with storing the heap like a regular binary tree :) The best way I know to solve this would be to thread the tree ( en.wikipedia.org/wiki/Threaded_binary_tree ), so as you are making it store an extra pointer for the next element you are looking for. Looking for this next element every time you need it doesn't seem efficient to me, so you have to store some information as you go one way or another. – Sulk

Or you could look into that more efficient way of building it that I was mentioning earlier. The idea is that you first just build the tree and don't worry about the heap properties, by just inserting elements as you get them and after you've inserted all the elements, then you start enforcing the heap property. Wikipedia explains it well I think: en.wikipedia.org/wiki/Binary_heap#Building_a_heap – Sulk

I took the latter approach. But I still face the same problem. How do I make the lastNode point to the parent.right after parent.left node has been populated with children? I mean I can do it with ease if there are only one or two levels, but it increases exponentially. – Joiejoin

It is after all homework, I think you have to figure out some things. There are several ways to do this. Here's a hint for one. I'm assuming since this is on heaps that you've already studied the more basic data structures. Think about how you could use any of those to solve your problem. Also think about other ways you could just arbitrarily place elements in a tree. – Sulk

Well, I'm trying to place them arbitrarily in the tree. However, the only problem I'm running into is how to do it from left to right. Can you be a little more specific? – Joiejoin

Answer 2

Since you have to insert nodes at the bottom level, ie breadth wise , what if you maintain a record of all nodes inserted so far in a queue? When you insert a new node in the heap, find the latest position from the queue and insert the data there. Then heapify_up that node.

Blowgun

Answer 3

I guess one more way of doing this would be to keep the count of all child elements for each node in the Tree. Since the main aim of the Binary heap is to be completely balanced, you can decide to insert the new node or they key, either towards the left or the right depending upon which side the tree is less balanced.

I am currently trying to write the Binary Hep code using Java and am stuck at this very same point. I have come up with this approach of balancing my Heap as well as solve the problem of where to insert the new node. This should still maintain the complexities of the Heap implementation.

Will post the code in sometime. If someone sees any issues with this or think that this is not the right way to do it, please do correct me.

Update: Here's the code (https://gist.github.com/naveenwashere/5607516):

public class BinaryHeap {

//Later you can implement a resizable array logic.
int[] bH;

public BinaryHeap(int N)
{
    bH = new int[N + 1];
}

//Index of the root
int k = 1;

//The APIs
public void put(int key)
{
    //Place the element at the end of the array
    bH[this.k] = key;       
    if(bH[this.k] > bH[this.k/2])
    {
        //since the elements in an array implementation of the binary heap is put at the end of the array,
        //we must always check if the property of the tree holds true or not.
        swim(this.k);
    }
    this.k++;
}

public void deleteMax()
{
    //Replace the element in the root with the element at the end of the array
    bH[1] = bH[k];
    //Restore the order of the tree
    sink(1);
    this.k--;
}

public void deleteMin()
{
    bH[this.k - 1] = 0;
    this.k--;
}

public void swim(int k)
{
    while((k != 1) && (bH[k] > bH[k/2]))
    {
        swap(k, k/2);
        k = k/2;
    }
}

public void sink(int k)
{
    while(2*k <= this.k)
    {
        int j = 2*k;
        if(max(j, j+1)) j++;
        if(bH[k] < bH[j])
            swap(k, j);
        else if(bH[k] > bH[j]) 
            break;
        k = j;
    }
}

private boolean max(int i, int j) {
    if(bH[i] < bH[j])
        return true;
    return false;
}

private void swap(int i, int j) {
    int temp = 0;
    temp = bH[i];
    bH[i] = bH[j];
    bH[j] = temp;
}

private void printAll() {
    for(int i=1; i < this.k; i++)
    {
        System.out.print(bH[i] + " ");
    }       
    System.out.println();
}

public static void main(String[] args) throws Exception
{
    int a[] = {6,5,7,8,2,9,8,1};
    BinaryHeap bh = new BinaryHeap(a.length);
    for(int i=0; i < a.length; i++)
    {
        bh.put(a[i]);
    }

    System.out.println("Elements in Binary Heap: ");
    bh.printAll();

    System.out.println("Deleting Minimum: ");
    bh.deleteMin();
    bh.printAll();

    System.out.println("Deleting Maximum: ");
    bh.deleteMax();
    bh.printAll();
}}

Thanks, ~N

Signal

Answer 4

I had the same homework assignment. The solution I found is to step down your binary tree level by level, each time deciding to make a left or a right turn depending on the number of nodes at the bottom. I made a recursive algorithm for this.

For example, say you want to place a new node in the following tree:

    A
   / \
  B   C
 / \ / \
D  E X  X

Starting at the top, you find that there are 2/4 full nodes at the bottom. Therefore you descend via the right branch and find yourself at the top of the tree with root C. At the bottom of this tree there are 0/2 full nodes, so you descend via the left branch and find yourself at a leaf node, so that is where you place the new element.

Here is the Java code I used to calculate the height of a tree, the number of possible nodes at the bottom of a tree with any given height, and the number of full or "used" nodes at the bottom of a tree with size size.

private int height(int size) {
    return (int) Math.ceil(log2(size + 1));
}
// returns the amount of space in the bottom row of a binary tree
private int bottomRowSpace(int height) {
    return (int) Math.pow(2, height - 1);
}
// returns the amount of filled spots in the bottom row of a binary tree
private int bottomRowFilled(int size) {
    return size - (bottomRowSpace(height(size)) - 1);
}
// log base2
private double log2(double a) {
    return Math.log(a) / Math.log(2);
}

Occupation

Answer 5

Use this function to reach desired node:

function find_node($n)
{
$current_node = $n;
while($current_node > 1)
{
    if($current_node % 2 == 1) // if node is odd it is a right child
    {
      push($stack,"Right");
    }
    else // otherwise it is even and left child
    {
      push($stack,"Left");
    }
    $current_node = floor($current_node / 2); // set the current node to the parent
}
return $stack; // this stack now contains the path to node n
}

Septemberseptembrist