4
\$\begingroup\$

I wrote a min-heap using a binary tree. How can I improve the time complexity of insert and delete function to be \$\mathcal{O}(log(n))\$?

'''
Min Heap Tree Implementation
'''

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

class HeapBT:
    def __init__(self):
        self.head = None

    def insert(self, data):
        if self.head is None:
            self.head = Node(data)
            return

        lst = []
        lst.append(self.head)
        while lst:
            currentNode = lst.pop(0)
            if currentNode.left is None:
                currentNode.left = Node(data)
                break

            if currentNode.right is None:
                currentNode.right = Node(data)
                break

            if currentNode.left is not None:
                lst.append(currentNode.left)

            if currentNode.right is not None:
                lst.append(currentNode.right)

        self.heapifyBottomUp(data)


    def bfs(self):
        if self.head is None:
            return
        lst = []
        lst.append(self.head)

        while lst:
            currentNode = lst.pop(0)
            print(currentNode.data)

            if currentNode.left is not None:
                lst.append(currentNode.left)

            if currentNode.right is not None:
                lst.append(currentNode.right)


    def heapifyBottomUp(self, data):
        count = 1
        while count:
            count = 0
            lst = []
            lst.append(self.head)
            while lst:
                currentNode = lst.pop(0)
                if currentNode.left is not None:
                    if currentNode.left.data == data:
                        if currentNode.data > currentNode.left.data:
                            count = 1
                            temp = currentNode.data
                            currentNode.data = currentNode.left.data
                            currentNode.left.data = temp
                            break

                    elif currentNode.left != data:
                        lst.append(currentNode.left)

                if currentNode.right is not None:
                    if currentNode.right.data == data:
                        if currentNode.data > currentNode.right.data:
                            count = 1
                            temp = currentNode.data
                            currentNode.data = currentNode.right.data
                            currentNode.right.data = temp
                            break

                    elif currentNode.right != data:
                        lst.append(currentNode.right)

    def heapifyTopDown(self, node):
        if node is None:
            return

        if node.left is not None and node.right is not None:
            if node.left.data < node.data and node.right.data < node.data:
                if node.left.data < node.right.data:
                    temp = node.data
                    node.data = node.left.data
                    node.left.data = temp
                    self.heapifyTopDown(node.left)
                    return

                else:
                    temp = node.data
                    node.data = node.right.data
                    node.right.data = temp
                    self.heapifyTopDown(node.right)
                    return

            elif node.left.data < node.data and node.right.data > node.data:
                temp = node.left.data
                node.left.data = node.data
                node.data = temp
                self.heapifyTopDown(node.left)
                return

            else:
                temp = node.right.data
                node.right.data = node.data
                node.data = temp
                self.heapifyTopDown(node.right)
                return

        elif node.left is not None:
            if node.left.data < node.data:
                temp = node.data
                node.data = node.left.data
                node.left.data = temp
                self.heapifyTopDown(node.left)
                return

        elif node.right is not None:
            if node.right.data < node.data:
                temp = node.data
                node.data = node.right.data
                node.right.data = node.data
                self.heapifyTopDown(node.right)
                return

    def pop(self):
        if self.head is None:
            return 'Heap is empty.'
        data = self.head.data
        if self.head.left is None and self.head.right is None:
            self.head = None
            return data
        lst = []
        lst.append(self.head)
        while lst:
            currentNode = lst.pop(0)

            if currentNode.left is not None:
                lst.append(currentNode.left)

            if currentNode.right is not None:
                lst.append(currentNode.right)

        leafData = currentNode.data

        lst = []
        lst.append(self.head)
        while lst:
            currentNode = lst.pop(0)

            if currentNode.left is not None:
                if currentNode.left.data == leafData:
                    currentNode.left = None
                    break
                else:
                    lst.append(currentNode.left)

            if currentNode.right is not None:
                if currentNode.right.data == leafData:
                    currentNode.right = None
                    break
                else:
                    lst.append(currentNode.right)


        self.head.data = leafData
        self.heapifyTopDown(self.head)

        return data

    def peek(self):
        if self.head is None:
            return 'self.head is None'

        return self.head.data


avl = HeapBT()

avl.insert(11)
avl.insert(10)
avl.insert(9)
avl.insert(8)
avl.insert(7)
avl.insert(6)
avl.insert(5)
avl.insert(4)
avl.insert(3)
avl.insert(2)
avl.insert(1)
avl.insert(-1)
avl.insert(43)
avl.insert(34)
avl.insert(53)
avl.insert(-1123)
avl.insert(-100)
avl.insert(-11233)

#avl.bfs()
print
print
print(avl.pop())
print(avl.pop())
print(avl.pop())
print(avl.pop())
print(avl.pop())
print(avl.pop())
print(avl.pop())
print(avl.pop())
print(avl.pop())
print(avl.pop())
print(avl.pop())
print(avl.pop())
print(avl.pop())
print(avl.peek(),'peek')
print

avl.bfs()
\$\endgroup\$
1
  • 2
    \$\begingroup\$ Is there a reason why you implement binary heap using a binary tree? It is much simpler to use a list to implement binary heap, with log performance on insert and delete. \$\endgroup\$
    – Christopher Boo
    Commented Oct 17, 2019 at 14:48

1 Answer 1

Reset to default
1
\$\begingroup\$

To achieve the \$\mathcal{O}(log(n))\$ time complexity of insert and delete functions you should store the binary tree as an array - Heap implementation. Because you need to have a link to the last element for performing insert and delete operations and the easiest (common) way to track this link is an array representation of the binary tree. You can devise your own method of tracking the last element for your binary tree representation, but I think it will be similar to the array method at the end.

My implementation:

class BinHeap:
    def __init__(self):
        self.lst = []

    def insert(self, data):
        self.lst.append(data)
        self.heapify_up(len(self.lst) - 1)

    def pop_root(self):
        root = self.lst[0]
        last = self.lst.pop()

        if len(self.lst) > 0:
            self.lst[0] = last 
            self.heapify_down(0, 0)

        return root

    def heapify_down(self, parent_idx, child_idx):
        if child_idx >= len(self.lst):
            return

        parent_greater_bool = self.lst[parent_idx] > self.lst[child_idx]

        if parent_greater_bool:
            self.lst[parent_idx], self.lst[child_idx] = self.lst[child_idx], self.lst[parent_idx]

        if parent_greater_bool or parent_idx == 0:
            self.heapify_down(child_idx, child_idx * 2 + 1)
            self.heapify_down(child_idx, child_idx * 2 + 2)

    def heapify_up(self, child_idx):
        parent_idx = (child_idx - 1) // 2

        if parent_idx < 0:
            return

        if self.lst[parent_idx] > self.lst[child_idx]: 
            self.lst[parent_idx], self.lst[child_idx] = self.lst[child_idx], self.lst[parent_idx]
            self.heapify_up(parent_idx)

Testing:

heap = BinHeap()

heap.insert(4)
heap.insert(5)

print(heap.lst)

print(heap.pop_root())
print(heap.pop_root())

print(heap.lst)

###Output:
# [4, 5]
# 4
# 5
# []

heap.insert(4)
heap.insert(5)
heap.insert(3)
heap.insert(7)
heap.insert(9)
heap.insert(10)
heap.insert(2)

print(heap.lst)

print(heap.pop_root())
print(heap.lst)

heap.insert(1)
print(heap.lst)

###Output:
# [2, 5, 3, 7, 9, 10, 4]
# 2
# [3, 5, 4, 7, 9, 10]
# [1, 5, 3, 7, 9, 10, 4]
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.