© The Author(s), under exclusive license to APress Media, LLC, part of Springer Nature 2022
R. WienerGeneric Data Structures and Algorithms in Gohttps://doi.org/10.1007/978-1-4842-8191-8_11

11. Heap Trees

Richard Wiener1  
(1)
Colorado Springs, CO, USA
 

The previous chapter presented AVL trees. These trees are extremely useful when many fast lookups are needed.

In this chapter, we present another important tree structure, Heap. A heap tree is another balanced tree type with the largest item in the tree always in the root of the tree. We use a heap tree to implement an efficient sorting algorithm.

In the next section, we define heap tree and illustrate heap tree construction.

11.1 Heap Tree Construction

A heap is a complete binary tree such that each node has a value greater than its two children. The largest value in a heap tree will always be in the root node. A complete tree has leaf nodes filled from left to right, all at the deepest level in the tree.

Consider the heap tree shown in the following. Each node has a value greater than its two children.

We wish to insert a new node with the value 90. See Figure 11-1.

An illustration of heap tree structure, presents max heap with number 100 on top, with three levels. Root node 100 has 2 subtrees 60 and 80. Left subtree: Node 60 has 2 child nodes 50 and 30. Node 50 has 2 child nodes 10 and 35. Right subtree: Node 80 has 2 child nodes 75 and 40. The node 30 on the left subtree is has a new node value 90 inserted.

Figure 11-1

Insertion of 90

We fill the leaf nodes from left to right, so node 90 needs to be the left node of 30. But 90 is larger than its parent 30. So we exchange the two nodes. See Figure 11-2.

An illustration of heap tree structure, presents max heap with number 100 on top, with three levels. Root node 100 has 2 subtrees 60 and 80. Left subtree: Node 60 has 2 child nodes 50 and 90. Node 50 has 2 child nodes 10 and 35. Node 90 has child node 30. Right subtree: Node 80 has 2 child nodes 75 and 40.

Figure 11-2

Insertion continued

But 90 is larger than its parent 60, so we do another exchange producing the new heap tree that contains 90. See Figure 11-3.

An illustration of heap tree structure, presents max heap with number 100 on top, with three levels. Root node 100 has 2 subtrees 90 and 80. Left subtree: Node 90 has 2 child nodes 50 and 60. Node 50 has 2 child nodes 10 and 35. Node 60 has child node 30. Right subtree: Node 80 has 2 child nodes 75 and 40.

Figure 11-3

Result after insertion

In the next section, we show how to perform deletion from a heap tree.

11.2 Deletion from a Heap Tree

We can only delete the value in the root node of a heap tree. To delete the root node value 100, we replace the value in the root node with the value in the rightmost node on the lowest level of the tree, 30 in this case. Then we compare the new root value with the values of its two children, swapping with the larger of the children. We continue this sift-down process until there are no further nodes to swap. So 30 gets swapped with 90 (the largest of the children, 90 and 80); then 30 gets swapped with 60 (the larger of the two children, 50 and 60). This leads to the new heap tree shown in Figure 11-4.

An illustration of heap tree structure, presents max heap with number 90 on top, with three levels. Root node 90 has 2 subtrees 60 and 80. Left subtree: Node 60 has 2 child nodes 50 and 30. Node 50 has 2 child nodes 10 and 35. Right subtree: Node 80 has 2 child nodes 75 and 40.

Figure 11-4

Result after deletion

In the next section, we examine the implementation details for building a generic heap tree from a slice of items and inserting a new item.

11.3 Implementation of a Heap Tree

Logic for Building a Heap Tree

The logic for building and inserting items in a heap tree flows from the following relationship between the index of an item in a slice and the location of that item in a heap tree. Suppose we have an item at a specified index.

  • Its parent is at location index / 2 if index is odd and at location index / 2 – 1 if index is even.

  • Its left child is at index 2 * index + 1.

  • Its right child is at index 2 * index + 2.

Consider the slice [90, 60, 80, 50, 30, 75, 40, 10, 35] that corresponds to the preceding heap tree. The slice values relate to the values in the heap tree by traversing the values from left to right at each succeeding level in the tree.

Consider the node with value 50 at index 3 in the slice.

The parent is at index 3 / 2, which equals 1. This corresponds to the node with value 60. The two children are at index values 2 * 3 + 1 and 2 * 3 + 2 or indices 7 and 8. This corresponds to the nodes with values 10 and 35.

Package Heap

Listing 11-1 presents a package for a generic heap, and Listing 11-2 shows a main driver program to test and exercise the methods of package heap.
package heap
type Ordered interface {
    ~float64 | ~int | ~string
}
type Heap[T Ordered] struct {
    Items []T
}
// Methods
func (heap *Heap[T]) Swap(index1, index2 int) {
    heap.Items[index1], heap.Items[index2] =
          heap.Items[index2], heap.Items[index1]
}
func NewHeap[T Ordered](input []T) *Heap[T] {
    heap := &Heap[T]{}
    for i := 0; i < len(input); i++ {
        heap.Insert(input[i])
    }
    return heap
}
func (heap *Heap[T]) Insert(value T) {
    heap.Items = append(heap.Items, value)
    heap.buildHeap(len(heap.Items) - 1)
}
func (heap *Heap[T]) Remove() {
    // Can only remove Items[0], the largest value
    heap.Items[0] = heap.Items[len(heap.Items)-1]
    heap.Items = heap.Items[:(len(heap.Items) - 1)]
    heap.rebuildHeap(0)
}
func (heap *Heap[T]) Largest() T {
    return heap.Items[0]
}
func (heap *Heap[T]) buildHeap(index int) {
    var parent int
    if index > 0 {
        parent = (index - 1) / 2
        if heap.Items[index] > heap.Items[parent] {
            heap.Swap(index, parent)
        }
        heap.buildHeap(parent)
    }
}
func (heap *Heap[T]) rebuildHeap(index int) {
    length := len(heap.Items)
    if (2 * index + 1) < length {
        left := 2*index + 1
        right := 2*index + 2
        largest := index
        if left < length && right < length &&
             heap.Items[left] >= heap.Items[right] &&
               heap.Items[index] < heap.Items[left] {
            largest = left
        } else if right < length &&
            heap.Items[right] >= heap.Items[left] &&
               heap.Items[index] < heap.Items[right]{
            largest = right
        } else if left < length && right >= length &&
               heap.Items[index] < heap.Items[left] {
            largest = left
        }
        if index != largest {
            heap.Swap(index, largest)
            heap.rebuildHeap(largest)
        }
    }
}
Listing 11-1

Package heap

package main
import (
    "fmt"
    "example.com/heap"
)
func main() {
    slice1:= []int{100, 60, 80, 50, 30, 75, 40, 10, 35}
    heap1 := heap.NewHeap[int](slice1)
    heap1.Insert(90)
    fmt.Println("heap1 after inserting 90")
    fmt.Println(heap1.Items)
    fmt.Println("Largest item in heap: ", heap1.Largest())
    heap1.Remove()
    fmt.Println("Removing largest item from heap
                 yielding the heap: ")
    fmt.Println(heap1.Items)
    fmt.Println("Largest item in heap: ", heap1.Largest())
    slice2:= []int{10, 35, 100, 80, 30, 75, 40, 50, 60}
    heap2 := heap.NewHeap[int](slice2)
    heap2.Insert(90)
    fmt.Println("heap2 with rearranged slice2 after inserting 90")
    fmt.Println(heap2.Items)
}
/* Output
heap1 after inserting 90
[100 90 80 50 60 75 40 10 35 30]
Largest item in heap:  100
Removing largest item from heap yielding the heap:
[90 60 80 50 30 75 40 10 35]
Largest item in heap:  90
heap2 with rearranged slice2 after inserting 90
[100 90 75 60 80 35 40 10 50 30]
*/
Listing 11-2

Main driver for heap

Explanation of Package heap

The generic Heap structure is given by a struct containing a slice of generic ordered type T.
type Heap[T Ordered] struct {
    Items []T
}

We focus on the function NewHeap and on the methods Insert and Remove. The other methods are much simpler and do not need explanation.

To build a heap from a slice of some ordered type T, we perform
func NewHeap[T Ordered](input []T) *Heap[T] {
    heap := &Heap[T]{}
    for i := 0; i < len(input); i++ {
        heap.Insert(input[i])
    }
    return heap
}

The first line of code defines a heap as the address (since we are returning a pointer to a Heap) of Heap with an empty slice of Items.

A for-loop follows that invokes the Insert method on each item in the input slice.

The Insert method, given as
func (heap *Heap[T]) Insert(value T) {
    heap.Items = append(heap.Items, value)
    heap.buildHeap(len(heap.Items) - 1)
}

appends the input value to the heap.Items slice. It then invokes the private method buildHeap.

This private method buildHeap directly follows the example shown in Section 11.1 and works upward from the bottom of the tree doing swaps when necessary to produce a heap.

The Remove method, given as
func (heap *Heap[T]) Remove() {
    // Can only remove Items[0], the largest value
    heap.Items[0] = heap.Items[len(heap.Items)-1]
    heap.Items = heap.Items[:(len(heap.Items) - 1)]
    heap.rebuildHeap(0)
}

assigns the item in the lowest rightmost position to index 0 in the heap.Items slice. It then reassigns this slice to exclude this rightmost item. The heap structure is temporarily broken by placing the deepest, rightmost value in the root. A private method rebuildHeap is invoked, which restores the heap property.

The method rebuildHeap is closely reasoned and requires care in understanding how it works. At each level of recursion, the item at index is initially assumed to be the largest. The values at index left and index right (or just left if right is out of range) are compared. If the value at index is less than the larger of the children, largest is set to the index of the larger child. Then a swap of values between value at index and largest is made, and a recursive call to rebuildHeap is made with parameter largest sent into rebuildHeap. Upon the completion of this method, the heap structure is restored.

Since a heap is close to perfectly balanced, its height is related to the number of nodes with a logarithmic relationship, height = log2n, where n is the number of nodes. Therefore, the methods buildHeap and rebuildHeap have complexity O(log2n).

In the main driver program, a second heap, heap2, is constructed using the same input integers but arranged in a different order. The resulting tree is indeed a heap but with a slightly different sequence of values in the slice.

In the next section, we examine an important application of a heap tree – a sorting algorithm, heap sort.

11.4 Heap Sort

The heap tree provides the basis for a sorting algorithm. It works as follows:

Build a heap from the initial list to be sorted. Extract the largest from the root and append it to the result list (initialized to empty). Apply the Remove method to the heap. Continue this process until the heap is shrunk to empty.

This process will produce a slice sorted from largest to smallest. We can produce output in ascending order by reversing the sequence in the slice produced previously.

The details of heap sort are presented in Listing 11-3.
package main
import (
    "example.com/heap"
    "fmt"
    "math/rand"
    "time"
)
type Ordered interface {
    ~float64 | ~int | ~string
}
func heapSort[T Ordered](input []T) []T {
    heap1 := heap.NewHeap[T](input)
    descending := []T{}
    for {
        if len(heap1.Items) > 0 {
            descending = append(descending, heap1.Largest())
            heap1.Remove()
        } else {
            break
        }
    }
    ascending := []T{}
    for i := len(descending) - 1; i >= 0; i-- {
        ascending = append(ascending, descending[i])
    }
    return ascending
}
const size = 50_000_000
func IsSorted[T Ordered](data []T) bool {
    for i := 1; i < len(data); i++ {
        if data[i] < data[i-1] {
            return false
        }
    }
    return true
}
func main() {
    slice := []float64{0.0, 2.7, -3.3, 9.6, -13.8, 26.0, 4.9, 2.6, 5.1, 1.1}
    sorted := heapSort[float64](slice)
    fmt.Println("After heapSort on slice: ", sorted)
    data := make([]float64, size)
    for i := 0; i < size; i++ {
        data[i] = 100.0 * rand.Float64()
    }
    start := time.Now()
    largeSorted := heapSort[float64](data)
    elapsed := time.Since(start)
    fmt.Println("Time for heapSort of 50 million floats: ", elapsed)
    if !IsSorted[float64](largeSorted) {
        fmt.Println("largeSorted is not sorted.")
    }
}
/* Output
Elapsed time for regular quicksort = 5.382400384s  (from Chapter 1)
Elapsed time for concurrent quicksort = 710.431619ms (from Chapter 1)
After heapSort on slice:  [-13.8 -3.3 0 1.1 2.6 2.7 4.9 5.1 9.6 26]
Time for heapSort of 50 million floats:  23.978801647s
*/
Listing 11-3

Heap sort

Discussion of heapsort Results

The complexity of heapsort is O(nlog2n) since the complexity of buildHeap and rebuildHeap is log2n, and we do this n times.

Comparing the time to sort 50 million floating-point numbers with quicksort or concurrent quicksort, we see that heapSort is about four times slower than quicksort.

In the next section, we examine another application of Heap, a priority queue.

11.5 Heap Application: Priority Queue

A heap provides a natural model for a priority queue. Each item is assumed to encapsulate a priority. For example, if we insert string values into the priority queue, we assume that the larger the string in a lexical sense, the higher its priority. So the string “Zachary” has a higher priority than the string “Robert”.

Listing 11-4 shows an implementation of priority queue using heaps.
package main
import (
    "example.com/heap"
    "fmt"
)
type Ordered interface {
    ~float64 | ~int | ~string
}
type PriorityQueue[T Ordered] struct {
    infoHeap heap.Heap[T]
}
// Methods
func (queue *PriorityQueue[T]) Push(item T) {
    queue.infoHeap.Insert(item)
}
func (queue *PriorityQueue[T]) Pop() T {
    returnValue := queue.infoHeap.Largest()
    queue.infoHeap.Remove()
    return returnValue
}
func main() {
    myQueue := PriorityQueue[string]{}
    myQueue.Push("Helen")
    myQueue.Push("Apollo")
    myQueue.Push("Richard")
    myQueue.Push("Barbara")
    fmt.Println(myQueue)
    myQueue.Pop()
    fmt.Println(myQueue)
    myQueue.Push("Arlene")
    fmt.Println(myQueue)
    myQueue.Pop()
    myQueue.Pop()
    fmt.Println(myQueue)
}
/* Output
{{[Richard Barbara Helen Apollo]}}
{{[Helen Barbara Apollo]}}
{{[Helen Barbara Apollo Arlene]}}
{{[Arlene Apollo]}}
*/
Listing 11-4

Priority queue using heap

11.6 Summary

In this chapter, we defined a heap structure and presented an implementation. Building a heap from a slice of items guarantees that the largest item is in the root node. Every item in a heap is larger than its left and right child items. We used a heap to implement an efficient sorting algorithm. We also used a heap to implement a priority queue.

In the next chapter, we introduce and implement red-black trees.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
18.119.133.96