Heaps

Experiment with larger inputs; what can you observe from the number of swaps performed?

With larger inputs, there will be more swaps performed, especially if the inputs are not sorted and are randomized. There will more bubble up and trickle down operations performed. However, if there will be less outputs, like what we have in our sample inputs, we would have less number of swaps and operations. However, it still depends on the “sortedness” of our randomized inputs.

Here, I experimented with a larger input.

Same as in the sample inputs, the first number is how many numbers in that test case. For this, I chose 100 random integers, which is from 1 to 100 in random order.

Here is the output. I’ve got many Bubble Ups and Trickle Downs.

Discuss the benefit of a BinaryHeap over a balanced binary search tree.

First of all, the binary heap will be most of time, a complete binary tree, with the leaf nodes at the far left. And if ever the child node will be bigger than its parent, the values of both will be swapped. There isn’t much movement in binary heap also. What I observed here in binary heap is that we always remove in the root, and we also add the new data in the last available position in the heap. However, the most beneficial trait that binary heap has over a balanced binary search tree is that binary heaps use arrays, rather than keeping track of specific individual nodes with their contents and pointers. In binary heaps, we can access everything in the array / list we made for it. Interestingly enough, we can somewhat traverse and iterate through the parent, and the child nodes with the given formulas. I think that binary heaps are more efficient especially when we have bigger data. Accessing data is fast too, because it will be in O(1) as compared in BST which is on average, O(log n).

Code Used:

class BinaryHeap:
    def __init__(self, capacity):
        self.storage = [0] * capacity
        self.capacity = capacity
        self.size = 0
        self.trickleDownCount = 0
        self.bubbleUpCount = 0

    # index helper functions
    def getParentIndex(self, index): # gets the parent index
        return (index - 1) // 2
    
    def getLeftChildIndex(self, index): # gets the left child index
        return (2 * index) + 1
    
    def getRightChildIndex(self, index): # gets the left child index
        return (2 * index) + 2

    # checker helper functions
    def hasParent(self, index): # checks if the node has a parent
        return self.getParentIndex(index) >= 0 
    
    def hasLeftChild(self, index): # checks if the node has a left child
        return self.getLeftChildIndex(index) < self.size 
    
    def hasRightChild(self, index): # checks if the node has a right child
        return self.getRightChildIndex(index) < self.size 

    # value helper functions
    def parent(self, index): # gets the parent value
        return self.storage[self.getParentIndex(index)] 
    
    def leftChild(self, index): # gets the left child value
        return self.storage[self.getLeftChildIndex(index)]

    def rightChild(self, index): # gets the right child value
        return self.storage[self.getRightChildIndex(index)]

    # other helper functions
    def isFull(self): # checks if the heap is full or not
        return self.size == self.capacity
    
    def swap(self, index1, index2): # swapper function
        temp = self.storage[index1]
        self.storage[index1] = self.storage[index2]
        self.storage[index2] = temp

    # main functions
    def add(self, data):
        if self.isFull():
            raise("Heap is Full")
        self.storage[self.size] = data # puts the data in the last available position 
        self.size += 1
        self.bubbleUp()

    def bubbleUp(self):
        index = self.size - 1 # gets the last element of the heap; the recently added node
        while self.hasParent(index) and self.parent(index) > self.storage[index]: # checks if the node has a parent
            self.bubbleUpCount += 1
            self.swap(self.getParentIndex(index), index) # swaps the recently added node with its parent
            index = self.getParentIndex(index) # goes further up in the tree until it terminates in the root

    def remove(self):
        if self.size == 0:
            raise("Empty Heap")
        data = self.storage[0] # save the data at the root node
        self.storage[0] = self.storage[self.size - 1] # replaces the root node with the last element of the heap
        del self.storage[self.size - 1]
        self.size -= 1 
        self.trickleDown()
        return data # returns the data from the root of the heap that was removed

    def trickleDown(self):
        index = 0 # starts at the root node and goes down to the tree
        while self.hasLeftChild(index): # while there is a left child (in this case, if there is still a node other than the root), 
            self.trickleDownCount += 1
            smallerChildIndex = self.getLeftChildIndex(index) 
            if self.hasRightChild(index) and (self.rightChild(index) < self.leftChild(index)): # checks if the right child is smaller than the left child of the current node 
                smallerChildIndex = self.getLeftChildIndex(index)
            if self.storage[index] < self.storage[smallerChildIndex]: # checks if the parent is smaller than the its child
                break
            else:
                self.swap(index, smallerChildIndex) # swaps the value of the current index its child if the child is smaller
            index = smallerChildIndex # goes down to the tree
            

input_dat = []

# reading input.dat
with open('input.dat', 'r') as input:
    input.readline()
    for line in input:
        input_dat.append(line.split())

    _input_dat = []
    for input in input_dat:
        _input_dat.append(input[1:])

# evaluating each test case
for i in _input_dat:
    heap = BinaryHeap(len(i))
    for j in i:
        heap.add(int(j))
    
    sorted_contents = heap.storage
    # print(sorted_contents)
    # sorted_contents = "".join(str(sorted_contents))
    _sorted_contents = []

    for content in sorted_contents:
        _sorted_contents.append(str(content))

    while heap.size:
        heap.remove()

    # print("Bubble Up: %d || Trickle Down: %d" % (heap.bubbleUpCount, heap.trickleDownCount))
    # print(_sorted_contents)
    # print()
    print(f"{heap.bubbleUpCount} {heap.trickleDownCount}", end=" ")
    for i in _sorted_contents:
        print(i, end=' ')
    print()


# For reference, I used this video
# https://www.youtube.com/watch?v=hkyzcLkmoBY&t=1545s

Sample Input

3
10 172 1 130 436 200 155 484 77 147 302
20 138 252 190 225 155 403 408 124 196 322 237 270 351 215 409 57 346 328 431 305 
30 251 380 86 177 381 322 74 365 175 373 182 108 210 429 410 242 131 415 255 352 13 491 374 429 310 209 394 173 441 212

Sample Output

4 13 1 77 130 147 200 155 484 436 172 302 
12 36 57 124 190 138 225 270 215 155 196 305 237 403 351 408 409 252 346 328 431 322 
25 47 13 74 86 175 131 108 173 177 255 182 373 310 209 251 212 380 242 415 365 381 352 491 374 429 322 210 394 429 441 410