File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
Win a copy of Clojure in Action this week in the Clojure forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

what is a binary heap?

 
Frederik Vig
Greenhorn
Posts: 1
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hey, can someone tell what a binary heap is? I've surched through a bunch of textbooks without finding a clear answer.
[ May 31, 2005: Message edited by: Frederik Vig ]
 
Svend Rost
Ranch Hand
Posts: 904
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi,

A binary heap is a complete binary tree.

Let me elaborate:

- It's a heap, so every node n (other than the root), is greater than it's
parent.
- It's a complete binary tree, that is it's a tree T, where all the levels
in the tree have the maximum number of nodes possible.

Example:


Feel free to reply back, if you need further explaination.

/Svend Rost
 
Adam Vinueza
Ranch Hand
Posts: 76
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Another way of talking about a binary heap is as a binary tree which has the property of being heap-ordered and left-to-right filled. A tree is heap-ordered if, given an ordering operator, the parent node is no later in the ordering than its children. Being left-to-right filled means that if there is a space available on a level, nodes are added left-to-right.

The space property of binary heaps makes them complete binary trees, except possibly for the lowest level. It is the heap property that makes them heaps.

Any decent data structures text should have basic information on binary heaps. They're usually just called heaps in your more basic texts, and are often discussed in the context of sorting, because binary heaps provide an efficient means for sorting items. A very good and comprehensive discussion is in the chapter on Heapsort in the big Intro to Algorithms book by Cormen et al.
[ May 31, 2005: Message edited by: Adam Vinueza ]
 
I agree. Here's the link: http://aspose.com/file-tools
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic