The Artima Developer Community
Articles | News | Weblogs | Books | Forums
Artima Forums | Articles | Weblogs | Java Answers | News
Sponsored Link •

.NET Buzz Forum
Binary Heaps

0 replies on 1 page.

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic   Next Topic
Flat View: This topic has 0 replies on 1 page
David Cumps

Posts: 319
Nickname: cumpsd
Registered: Feb, 2004

David Cumps is a Belgian Student learning .NET
Binary Heaps Posted: Feb 14, 2005 6:29 AM
Reply to this message Reply

This post originated from an RSS feed registered with .NET Buzz by David Cumps.
Original Post: Binary Heaps
Feed Title: David Cumps
Feed URL: http://weblogs.asp.net/cumpsd/rss?containerid=12
Feed Description: A Student .Net Blog :p 		Latest .NET Buzz Posts
Latest .NET Buzz Posts by David Cumps
Latest Posts From David Cumps

Advertisement

A pathfinder has to be very fast, but when we take a look at the performance we notice that working with the open-list is the bottleneck.

There are several possible data structures to store the open-list. We could use an ArrayList to store the values and keep it sorted using an IComparable interface. With this solution we end up with too much overhead keeping the entire list sorted. After all, the only thing our pathfinder is interested in, is the node with the lowest F-score, it doesn’t care about the other nodes.

A better solution is using a binary heap. In a binary heap, each item has two children with a value higher or equal to itself. Which means in the end the lowest item is at the top of the heap, easily accessible.



One of the nice things of a binary heap is the fact that it can be stored in a 1-dimensional array, making sorting of the heap a very quick operation.

The top of the heap is always stored at index 1. We don’t use the 0-index when working with zero-based arrays.



The children of any given item are always stored at the item’s location * 2 and the item’s location * 2 + 1. For example, in the image given above, the item with value 20 is stored at index 3 and its two children can be found at index 6 (3 * 2) and index 7 (3 * 2 + 1).

Adding an item to a binary heap can be achieved by adding the new item at the end of the array and then letting the new item bubble its way up.

This is achieved by comparing the item with its parent, swapping them when the item is smaller then its parent and repeating this until the parent is smaller.

 

public void Add(Int32 fCost) {

  this.binaryHeap[this.numberOfItems] = fCost;

  

  Int32 bubbleIndex = this.numberOfItems;

  while (bubbleIndex != 1) {

    Int32 parentIndex = bubbleIndex / 2;

    if (this.binaryHeap[bubbleIndex] <= this.binaryHeap[parentIndex]) {

      Int32 tmpValue = this.binaryHeap[parentIndex];

      this.binaryHeap[parentIndex] = this.binaryHeap[bubbleIndex];

      this.binaryHeap[bubbleIndex] = tmpValue;

      bubbleIndex = parentIndex;

    } else {

      break;

    }

  }             

  this.numberOfItems++;

} /* Add */


To remove an item from a binary heap, we simply take the item at index 1. But now we have to repair our heap, because there is a gap at the top. To fix this we take the last item and place it at the top, after which we let it sink downwards. This is done by comparing the value with its two children, replacing it with the smallest child and repeating this until the parent is smaller than both children.

 

public BinaryHeapItem Remove() {

  this.numberOfItems--;

  Int32 returnItem = this.binaryHeap[1];

 

  this.binaryHeap[1] = this.binaryHeap[this.numberOfItems];

 

  Int32 swapItem = 1, parent = 1;

  do {

    parent = swapItem;

    if ((2 * parent + 1) <= this.numberOfItems) {

      // Both children exist

      if (this.binaryHeap[parent] >= this.binaryHeap[2 * parent]) {

        swapItem = 2 * parent;

      }

      if (this.binaryHeap[swapItem] >= this.binaryHeap[2 * parent + 1]) {

        swapItem = 2 * parent + 1;

      }

    } else if ((2 * parent) <= this.numberOfItems) {

      // Only one child exists

      if (this.binaryHeap[parent] >= this.binaryHeap[2 * parent]) {

        swapItem = 2 * parent;

      }

    }

    // One if the parent's children are smaller or equal, swap them

    if (parent != swapItem) {

      Int32 tmpIndex = this.binaryHeap[parent];

      this.binaryHeap[parent] = this.binaryHeap[swapItem];

      this.binaryHeap[swapItem] = tmpIndex;

    }

  } while (parent != swapItem);

  return returnItem;

} /* Remove */


A small comparison between an ArrayList and this binary heap implementation gives the following results:

Binary Heap: added 4000 items.

Time needed: 00:00:00

Lowest F-score: 1

Sorted ArrayList: added 4000 items.

Time needed: 00:00:07.2968750

Lowest F-score: 1

 

Binary Heap: added 10000 items.

Time needed: 00:00:00.0156250

Lowest F-score: 1

Sorted ArrayList: added 10000 items.

Time needed: 00:00:56.1250000

Lowest F-score: 1


Inspiration and some images used from Patrick Lester.

Read: Binary Heaps

Topic: Personal Rant: Fighting for TechEd Sessions and mitigation ideas Previous Topic   Next Topic Topic: WSCF 0.5: New Features (VI)
Sponsored Links


Google
  Web Artima.com   

Copyright © 1996-2019 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use