A heap is an array-based binary tree. That is, the data structure is an array, which we view and handle as through it were a binary tree. Index calculations identify the children and parent of each node. Associated with the array is a Less or Greater comparator that defines a less than or a greater than relation between any pair of elements.
A heap has an order relationship between a parent and its children that is based on the type of comparator. For a maximum heap, the value of a parent is greater than or equal to the value of each of its children. For a minimum heap, the value of the parent is less than or equal to the value of each of its children. A maximum heap uses a Greater comparator and a minimum heap uses a Less comparator. These situations are depicted in below figure, which illustrates these two types of heaps. In a maximum heap, the root contains the largest element; in a minimum heap, the root contains the smallest element.
A heap is an array with an ordering among the elements that locates the largest(maximum) or smallest (minimum) element at index 0. A heap is not an independent data structure but rather an array ordering. Heaps have very efficient operations for inserting and deleting elements. The algorithms update the array to maintain heap ordering between parents and children. The ordering of elements and the associated insert and delete operations make a heap an ideal storage structure to implement a priority queue. The algorithms can be used to convert a general array to a heap. By exploiting the heap ordering on the array, we develop a fast array sort algorithm, called the heapsort. In this section, we focus on key help algorithms, which we implement as static generic methods in the class Heaps. The methods include a Comparator argument so that they apply to both a maximum and a minimum heap. Our discussion assumes we are working with a maximum heap and that the generic type for the array elements implements the Comparable interface.
We start with algorithms to insert and delete an element in a heap. We will use these operations in the implementation of the HeapPQueue class, which allocates a heap as the storage structure. For obvious reasons, we call the insert method pushHeap() and the delete method popHeap(). Each of these methods must ensure that heap ordering is maintained between parents and children. To this end, we will define a utility method called adjustHeap() that reassigns values along a path of nodes to reestablish the heap order.
Inserting into a Heap :
Inserting into a heap involves assigning a value to an element in the n-element array. The context assumes that the heap is an initial sublist of the array. That is, for some index, called last, the elements in the index range [0, last) are a heap and the elements in the index range [last, n) are not currently part of the heap. The new element will enter the array at index last with the heap expanding by one element. In below figure, the shaded boxes in the array correspond to the current nodes in the heap. An insertion occurs at index last=5 :
An insertion expands the heap to include index last. The new value initially enters the heap at index last. It must then be positioned somewhere on the path of parents, which begins at index last and proceeds up the tree to the root at index 0. We must add the value in such a way that heap order is maintained. Let us look at an example to appreciate the problem. Below figure(a) displays a heap with last=10. A new value 50 enters the heap at arr[10] and then is positioned along the path of parents arr[10], arr[4], arr[1], and arr[0] (figure(b)) :
The insert algorithm involves local repositioning of elements in the tree so that the heap order is maintained. The example illustrate what we mean by "local". If value 50 enters the heap at index 10, it would be out of order relative to its parent 25 and grand parent 30. The problem occurs along the path of parents and does not affect the other elements.
The static method pushHeap() inserts a new value in the heap. The parameter list includes the array arr, the index last, the new value item, and a Comparator object of type Greater or Less indicating whether the heap is a maximum or minimum heap. Our example assumes a maximum heap :
public static
The algorithm uses an iterative scan with variable currPos initially set to last. At each step, compare the value item with the value of the parent and if item is larger, copy the parent value to the element at index currPos and assign the parent index as the new value for currPos. The effect is to move the parent down one level. Stop when the parent is larger and assign item to the position currPos. For the detail process, please refer to below figure :
The method pushHeap() sets out along the path of parents to insert item. The indices currPos and parentPos move in tandem up the parent path, beginning with currPos = last. Below is the implementation :
Deleting from a Heap :
Deletion from a heap is normally restricted to the root only. Hence, the operation removes the maximum (or minimum) element. The static method popHea() implements the algorithm and then returns the deleted value. The parameter list includes the array and a Comparator object. The integer last specifies that only the elements in the index rang [0, last) comprise the heap :
public static
The algorithm begins by exchanging the root with the last element in the heap. The effect is to tuck the root away in a safe position. Unfortunately, the exchange can destroy the heap order: the new root might not be greater than or equal to its children. The algorithm then reestablish heap order in the tree, minus its last value, by moving the new root down a path of children until it finds a proper location.
Let us look at an example that illustrates the initial steps in the popHeap() algorithm. Below figure displays a heap before beginning a deletion and then immediately after we exchange the root with the last element in the tree. The exchange of 18 and 68 destroys the heap order, because the new root 18 is not greater than or equal to its children 30 o 40. Note that we consider only the blue elements as part of the remaining heap. To complete the deletion, we need to adjust the heap.
- Adjusting the Heap
The algorithm to delete the root node may need to reestablish heap order. This involves moving (filtering) the root down the tree along a path of children until it locates a valid position. For the heap in upper figure, we will move the target(root) value 18 down the path of larger children 40 and 38, moving each node up one level. As a result, 40 becomes the new root and 18 will be positioned at a leaf node. The filtering process has application beyond the deletion algorithm and so we promote code reuse by declaring a method, called adjustHeap(), that performs the tesks. The method has parameters that include the array, the integer first and last, and a Comparator object. The parameter first is the index of the element that must filter down the tree and parameter lastindicates that we will only check a child index that is less than last.
public static
We illustrate the iterative adjustHeap() algorithm when index first=0. This is the situation with popHeap(), where the root must move down the tree until we reestablish heap order. Start by comparing the root value(target) with the values of its two children. If the root is not greater than or equal to both children, heap order is violated. We select the larger child and move it up one level. The child then becomes the root. Shift the focus to the child position. The process continues until the target value is greater than or equal to both children or the current position is a leaf node. The target is assigned to this position and heap order is restored.
We illustrates the algorithm for the example in upper figure. The steps are displayed in below figure. The root 18 is the target. Because 18 is less than its children 30 and 40, the larger child 40 is moved up one level and the child position index 2, is the focus for the next step. At level1, 18 is greater than 8 but not 38 and so child 38 moves up one level. At level 2, the element arr[6] is a leaf node. Any value in a leaf node satisfies heap order because the node has no children. We have identified a valid position, which is then assigned the target value :
The implementation of adjustHeap() uses the integer variables currPos, target and childPos to scan the path of children. Initially, currPos is first and the targetis arr[first]. The iterative scan proceeds until we reach a leaf node or target is greater than or equal to the values of the children at the current position. If the latter condition is not true, we must identify the value of the larger child. At index currPos, the child indices are 2*currPos + 1 (left child) and 2*currPos + 2(right child). Initially, set childPos to be the index of the left child. If the value of the right child is greater, update childPos to this index. Both currPos andchildPos move down the path of children in tandem. When one of the stopping conditions is true, terminate the iterative process and assign target to arr[currPos].
- Implementing popHeap()
No matter whether the operation occurs in a maximum heap or a minimum heap, the root(arr[0]) holds the optimal value. The implementation first captures the optimal value and then exchanges it with the last value in the heap (arr[last-1]). A call to adjustHeap() reestablishes heap order in a heap which now has index range [0, last-1). Method popHeap() concludes by returning the optimal value.
- Program 22.1 : HEAP OPERATIONS
Let us look at a simple program that illustrates the heap methods. Array intArr is initialized with seven Integer values. The program creates uninitialized Integer arrays heapArray with the same number of elements as intArr :
Output :
Displaying a Heap :
For search tree, the method displayTree() returns a string that describes the hierarchical order of nodes in the tree. The methods displayHeap() do the same thing. The implementation is below :
Complexity of Heap Operations :
A heap stores elements in an array-based tree that is a complete tree. The pusHeap() and adjustHeap() operations reorder elements in the tree by moving up the path of parents or down the path of largest (smallest) children. Assuming the heap has n elements, the maximum length for a path between a leaf node and the root is log2n, so the runtime efficiency of the algorithms is O(log2n).
沒有留言:
張貼留言