Note_Tech

All technological notes.

---

Project maintained by simonangel-fong Hosted on GitHub Pages — Theme by mattgraham

DSA - Heap

Back

• DSA - Heap
  • Heap
  • Implementation: Max Heap
    • Children and parent nodes
    • Insert method

---

Heap

• Heap

• Properties:

---

Implementation: Max Heap

• use a list

Children and parent nodes

• Diagram

class MaxHeap:
    def __init__(self):
        self.heap = []

    def _left_child_index(self, index):
        '''
        Get the index of left child
        index: the index of the current node
        '''
        return 2 * index + 1

    def _right_child_index(self, index):
        '''
        Get the index of right child
        index: the index of the current node
        '''
        return 2 * index + 2

    def _parent(self, index)
        '''
        Get the index of parent node
        index: the index of the current node
        '''
        return (index -1) // 2

---

Insert method

# helping methods
def _swap(self, index1, index2):
    '''
    Swap two values of given indices
    index1: the first index
    index2: the second index
    '''

    self.heap[index1], self.heap[index2] = self.heap[index2], self.heap[index1]

---

TOP