PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (194)
Orphanage
Unclass'd
Unproven (498)
Corrections (25)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: High Entry average rating: No information on entry rating
heap (Data Structure)

Let $ \preceq$ be a total order on some set $ A$. A heap is then a data structure for storing elements in $ A$. A heap is a balanced binary tree, with the property that if $ y$ is a descendent of $ x$ in the heap, then $ x\preceq y$ must hold. This property is often referred to as the heap property.

If $ \preceq$ is $ \leq$, then the root of the heap always gives the smallest element of the heap, and if $ \preceq$ is $ \geq$, then the root of the heap always gives the largest element of the heap. More generally, the root of the heap is some $ a\in A$ such that $ a\preceq x$ holds for all $ x$ in the heap.

For example, the following heap represents the multiset $ \left\{ 1, 2, 4, 4, 6, 8 \right\}$ for the total order $ \geq$ on $ \mathbb{Z}$.

$\displaystyle \begin{xy} *!C\xybox{ \xymatrix{ &&& 8 \ar@{-}[dll] \ar@{-}[drr] \ & 4 \ar@{-}[dl] \ar@{-}[dr] &&&& 6 \ar@{-}[dl] \ 1 && 4 && 2 } } \end{xy}$

Due to the heap property, heaps have a very elegant application to the sorting problem. The heapsort is an in-place sorting algorithm centered entirely around a heap. Heaps are also used to implement priority queues.



Anyone with an account can edit this entry. Please help improve it!

"heap" is owned by mps. [ full author list (2) | owner history (1) ]
(view preamble)

View style:

See Also: binary tree, balanced tree, heap insertion algorithm, heap removal algorithm, heapsort

Also defines:  heap property
Log in to rate this entry.
(view current ratings)

Cross-references: queues, in-place sorting algorithm, heapsort, sorting problem, application, multiset, represents, root, property, balanced binary tree, structure, total order
There are 5 references to this entry.

This is version 3 of heap, born on 2002-02-25, modified 2004-05-17.
Object id is 2707, canonical name is Heap.
Accessed 9043 times total.

Classification:
AMS MSC: 68P10 (Computer science :: Theory of data :: Searching and sorting)
 68P20 (Computer science :: Theory of data :: Information storage and retrieval)
 68P05 (Computer science :: Theory of data :: Data structures)
Pending Errata and Addenda
None.
[ View all 1 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add example | add (any)