draw a tree representation for the following heap

---

This lecture covers Chapter 10 (Section 10.1) of our text book and documents from wikipedia. Applet.

---

Heaps

Definition: A heap is a specialized tree-based data structure that satisfied the heap property: if B is a child node of A, then key(A) ≥ key(B). This implies that an element with the greatest key is always in the root node, and so such a heap is sometimes called a max-heap. Of course, there's also a min-heap. Applications: A heap has many applications, including the most efficient implementation of priority queues, which are useful in many applications. In particular, heaps are crucial in several efficient graph algorithms. Variants: 2-3 heap Binary heap Many many others Binary heap storage rules  -- A heap implemented with a binary tree in which the following two rules are followed: The element contained by each node is greater than or equal to the elements of that node's children. The tree is a complete binary tree. Example: which one is a heap?

Heap Implementation

Adding an Element to a Heap Example: We want to insert a node with value 42 to the heap on the left. The above process is called reheapification upward. Pseudocode for Adding an Element: Place the new element in the heap in the first available location. This keeps the structure as a complete binary tree, but it might no longer be a heap since the new element might have a greater value than its parent. while (the new element has a greater value than its parent) swap the new element with its parent. Notice that Step 2 will stop when the new element reaches the root or when the new element's parent has a value greater than or equal to the new element's value. Removing the Root of a Heap The procedure for deleting the root from the heap -- effectively extracting the maximum element in a max-heap or the minimum element in a min-heap. The above process is called reheapification downward. Psuedocode for Removing the Root: Copy the element at the root of the heap to the variable used to return a value. Copy the last element in the deepest level to the root and then take this last node out of the tree. This element is called the "out-of-place" element. while (the out-of-place element has a value that is lower than one of its children) swap the out-of-place element with its greatest-value child. Return the answer that was saved in Step 1. Notice that Step 3 will stop when the out-of-place element reaches a leaf or it has a value that is greater or equal to all its children. Now, think about how to build a heap. Check out the example of inserting 27, 35, 23, 22, 4, 45, 21, 5, 42 and 19 to an empty heap.

Heap Implementation

A more common approach is to store the heap in an array. Since heap is always a complete binary tree, it can be stored compactly. No space is required for pointers; instead, the parent and children of each node can be found by simple arithmetic on array indices. The rules (assume the root is stored in arr[0]): For each index i, element arr[i] has children at arr[2i + 1] and arr[2i + 2], and the parent at arr[floor( ( i - 1 )/2 )]. This implementation is particularly useful in the heapsort algorithm, where it allows the space in the input array to be reused to store the heap (i.e., the algorithm is in-place). However it requires allocating the array before filling it, which makes this method not that useful in priority queues implementation, where the number of elements is unknown. It is perfectly acceptable to use a traditional binary tree data structure to implement a binary heap. There is an issue with finding the adjacent element on the last level on the binary heap when adding an element. Here's a method we can follow.

Building a Heap

A heap could be built by successive insertions. This approach requires O(n log n) time for n elements. Why? The optimal method: Starts by arbitrarily putting the elements on a binary tree. Starting from the lowest level and moving upwards until the heap property is restored by shifting the root of the subtree downward as in the removal algorithm. If all the subtrees at some height h (measured from the bottom) have already been "heapified", the trees at hight h+1 can be heapified by sending their root down. This process takes O(h) swaps. As an example, let's build a heap with the following values: 20, 35, 23, 22, 4, 45, 21, 5, 42 and 19. Click here to see the process. As has been proved here, this optimal method requires O(n) time for n elements.

Priority Queues

A priority queue behaves much like an ordinary queue: Elements are placed in the queue and later taken out. But each element in a priority queue has an associated number called its priority. When elements leave a priority queue, the highest priority element always leaves first. Heap Implementation of P.Q. In the heap implementation of a priority queue, each node of the heap contains one element along with the element's priority, and the tree is maintained so that it follows the heap storage rules using the element's priorities to compare nodes: The element contained by each node has a priority that is greater than or equal to the priorities of the elements of that node's children. The tree is a complete binary tree. A P.Q. Implementation Using an Ordinary Queue Define an array of ordinary queues, called queues[]. The items with priority 0 are stored in queues[0]. Items with priority 1 are stored in queues[1]. And so on, up to queues[highest]. When an item with priority i needs to be added, we insert it to the end of queues[i]. When an item needs to be removed, we move down through the ordinary queues, starting with the highest priority, until we find a nonempty queue. We then remove the front item from this nonempty queue. For efficiency, we could keep a variable to remember the current highest priority.

Exercises

What are the time complexities of insertion and removal of elements on a heap? In the description of reheapification downward, we specified that the out-of-place element must be swapped with the larger of its two children. Can we swap with the smaller child instead? Start with an empty heap and enter 10 elements with priories 1 through 10. Draw the resulting heap (max-heap). Remove three elements from the heap you created in the above heap. Draw the resulting heap.

Learning Objectives

After studying this subject, you should be able to: List the rules for a heap and determine whether a tree satisfies these rules. Insert a new element into a heap or remove the root from a heap. Use the heap data structure to implement a priority queue.

---

Last updated: Oct. 2010

davistogne1991.blogspot.com

Source: https://www.cpp.edu/~ftang/courses/CS241/notes/heap.htm

Share this post