DEV Community 👩‍💻👨‍💻

Jenny Yang
Jenny Yang

Posted on

Learning Algorithms - Heap | Part 02

Continuing from the last post, Heap Part 01, I would explain heap sort which happens when inserting and deleting items from a heap. Let me recap from what I covered last time. We were doing a min-heap example and its basic methods such as parent(), left_child(), right_child().

Violation

Violation in a heap is when a child node is greater than a parent node in max-heap or child node is less than a parent node in min-heap.

Insertion

We are going to have a look a trivial example of how items inserted, to understand the heap sort. To start with, we are going to insert 7, 1, 3 in the order.

insert(7)
insert(3)
insert(1)
Enter fullscreen mode Exit fullscreen mode

1_618hbhp2YozrVFx8fkaTRg
Did you notice? every time we inserted an item, there will be a comparison of two items, a parent and child, and swap the two when there is a violation. Continuing inserting items from the given example.

insert(20)
insert(11)
insert(9)
Enter fullscreen mode Exit fullscreen mode

1_4bLTQShx0QXjrBw98_BT6w
We inserted 7, 3, 1, 20, 11 and 9 so far. There has not been any swap in the second round. Moving on to the next round.

insert(3)
insert(15)
insert(4)
insert(13)
Enter fullscreen mode Exit fullscreen mode

1__2pQBv-hY4ZZT2QoVJUg4A
We swapped 20 and 15 as 15 is smaller than its parent 20, and moving on to parent node 7, the parent 7 is smaller than its child 15, so it is all sorted.

1_t_i1vuStGBajPEEFPM1pjA
There are two comparisons 4 and 15, 4 and 7, the number 4 initially inserted in [9] and moved up to [2] as it is swapped with its parent each time. Last round is to insert 13, hang in there till the end.

Final result

1_Y9pSpbkGyw8aN4BcwzEqWw

Extract min

Extract min is the deletion method in a heap. In a big picture, there are two steps:

  1. deletion: swap [1] and [n] where n = length of a heap exclude [0] and delete the [n] which is the min item.
  2. heap sort: swap until the item in [1] is smaller than its children.

step 1: deletion

1_1TZ3pO2aDWjvPTbLgNcy1A

step 2: heap sort

1_ONI2tFtXRB4i3NodEEF6-Q

Swap

Swap method is simply swapping two items and will be used in heapify() method.

def swap(self, a, b):
    self.heap[a], self.heap[b] = self.heap[b], self.heap[a]
Enter fullscreen mode Exit fullscreen mode

Heapify

Whenever there is a violation in heap properties, we are going to correct the violation by swapping a child and a parent. What I mean by violation is, when a child is less than its parent in min-heap. There would be two ways of implementation using recursion or iteration. Insertion and deletion always run heapify at the end of the execution to keep to sort the heap.

Iteration

def heapify(self, i):
    parent = i // 2
    """ 
    as long as the element is in the range of index of a heap 
    (0 is not included)
    """
    while i // 2 > 0:
        # if the element is bigger than its parent swap them
        if self.heap[i] < self.heap[parent]:
            self.swap(parent, i)

        # move the index to the parent
        i = i // 2
Enter fullscreen mode Exit fullscreen mode

Let me break down the code line by line.

  1. while i // 2 means as long as the in the range (from 1 to n)
  2. self.heap[i] < self.heap[parent] if the current node is less than its parent, swap those two since parent should be smaller.
  3. i = i // 2 means bubble up to its parent to keep checking the violation.

Note: i in this heapify is self.size which refers to the last index

Recursion

def heapify(self, i):
    l = self.left(i)
    r = self.right(i)
    smallest = i

    """
    if the r and l are within the range of index,
        and if one of those are smaller than i,
        swap them with i
    """
    if l <= self.size and self.heap[l] < self.heap[i]:
        smallest = l
        print(f"now smallest is {self.heap[l]}")
        self.swap(i, smallest)
    if r <= self.size and self.heap[r] < self.heap[i]:
        smallest = r
        self.swap(i, smallest)

    """
    recursively do the process(heapify) above
    until i becomes smallest in the three relationships in the tree
    """
    if smallest != i:
        self.heapify(i)
Enter fullscreen mode Exit fullscreen mode
Break down:

i = parent node
there are three pointers that refer to the left child, right child and smallest. In here, the important thing to remember in here i ≤ l or r.
if l or r are within the range of index and one of those are smaller than i, then swap them with i since i should be the smallest.

  1. recursively do the process until i becomes smallest amongst the three (left child, right child, parent i).

Implementation

The two insertions are basically the same, the argument the heapify method receives varies due to different heapify method. Firstly, appending a new node then increase size. Lastly, sorting the heap.

Insertion: iteration

def insert(self, key):
    self.heap.append(key)
    self.size += 1
    # Fix violation if there is one
    # iteration heapify
    self.heapify(self.size)
Enter fullscreen mode Exit fullscreen mode

In iterative insertion, the heapify takes the last index.

Insertion: recursion

def insert(self, key):
    self.heap.append(key)
    self.size += 1
    # Fix violation if there is one
    # recursion heapify
    self.heapify(self.size // 2)
Enter fullscreen mode Exit fullscreen mode

In recursive insertion, the heapify takes the parent index of the last item.

The time complexity of insertion is appending O(1) + size alteration O(1) + heapify O(log n) = O(log n)

Deletion (extract min)

Code break down:

  1. store the item to delete
  2. swap the root item with the last one
  3. delete the last item that where there is min item
  4. heap sort until it meets the criteria
  5. return the removed item
def extract_min(self):
    popped = self.heap[1]
    # swap last item and the root(min) item
    self.swap(self.size, 1)
    # pop the last item off
    self.heap.pop()
    # reduce size of the heap as an item is deleted
    self.size -= 1
    # sort the heap
    self.heapify(1)
    # return the popped item
    return popped
Enter fullscreen mode Exit fullscreen mode

Easy peasy, yeah?

The time complexity of deletion is swap O(1) + deletion O(1) + size alteration O(1) + heapify O(log n) = O(log n)

Time analysis

Heapify plays a key role in this algorithm. Because other steps in insertion and deletion are constant time, what we really care about is the heapify method. Let me explain why heapify takes logarithmic time.

1_2NnifXR3HQjk1efoppNkkQ
If N = 9, the heapify will take a maximum of 4 steps in the worst case, therefore the height of the tree would be the time to process the heapify function. Let's substitute the N to logarithm formula.

1_zlt2J9xnjYBCKoY5ANPzDQ

2³ is roughly equal to 9, hence the heapify is O(log N)

I still have one advanced method to explain. I will see you in part 3!

Top comments (0)

Image description

Join the One Year Club

You can earn this badge by being a registered member of the DEV Community for at least one year. Create an account and get started today.