Java Reference
In-Depth Information
synonymous because the logical view of the heap is actually a tree structure, while
the typical physical implementation uses an array.
Figure 5.19 shows an implementation for heaps. The class is a generic with one
type parameter, E , which defines the type for the data elements stored in the heap.
E must extend the Comparable interface, and so we can use the compareTo
method for comparing records in the heap.
This class definition makes two concessions to the fact that an array-based im-
plementation is used. First, heap nodes are indicated by their logical position within
the heap rather than by a pointer to the node. In practice, the logical heap position
corresponds to the identically numbered physical position in the array. Second, the
constructor takes as input a pointer to the array to be used. This approach provides
the greatest flexibility for using the heap because all data values can be loaded into
the array directly by the client. The advantage of this comes during the heap con-
struction phase, as explained below. The constructor also takes an integer parame-
ter indicating the initial size of the heap (based on the number of elements initially
loaded into the array) and a second integer parameter indicating the maximum size
allowed for the heap (the size of the array).
Method heapsize returns the current size of the heap. H.isLeaf(pos)
returns true if position pos is a leaf in heap H , and false otherwise. Members
leftchild , rightchild , and parent return the position (actually, the array
index) for the left child, right child, and parent of the position passed, respectively.
One way to build a heap is to insert the elements one at a time. Method insert
will insert a new element V into the heap. You might expect the heap insertion pro-
cess to be similar to the insert function for a BST, starting at the root and working
down through the heap. However, this approach is not likely to work because the
heap must maintain the shape of a complete binary tree. Equivalently, if the heap
takes up the first n positions of its array prior to the call to insert , it must take
up the first n + 1 positions after. To accomplish this, insert first places V at po-
sition n of the array. Of course, V is unlikely to be in the correct position. To move
V to the right place, it is compared to its parent's value. If the value of V is less
than or equal to the value of its parent, then it is in the correct place and the insert
routine is finished. If the value of V is greater than that of its parent, then the two
elements swap positions. From here, the process of comparing V to its (current)
parent continues until V reaches its correct position.
Since the heap is a complete binary tree, its height is guaranteed to be the
minimum possible. In particular, a heap containing n nodes will have a height of
(n log n). Intuitively, we can see that this must be true because each level that we
add will slightly more than double the number of nodes in the tree (the ith level has
2 i nodes, and the sum of the first i levels is 2 i+1 1). Starting at 1, we can double
only log n times to reach a value of n. To be precise, the height of a heap with n
nodes is dlog(n + 1)e:
Search WWH ::




Custom Search