Heap

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

int intArray[10];
int size;

bool isEmpty(){
   return size == 0;
}
int getMinimum(){
   return intArray[0];
}
int getLeftChildIndex(int nodeIndex){
   return 2*nodeIndex +1;
}
int getRightChildIndex(int nodeIndex){
   return 2*nodeIndex +2;
}
int getParentIndex(int nodeIndex){
   return (nodeIndex -1)/2;
}
bool isFull(){
   return size == 10;
}
/**
* Heap up the new element,until heap property is broken. 
* Steps:
* 1. Compare node's value with parent's value. 
* 2. Swap them, If they are in wrong order.
* */
void heapUp(int nodeIndex){
   int parentIndex, tmp;
   if (nodeIndex != 0) {
      parentIndex = getParentIndex(nodeIndex);
      if (intArray[parentIndex] > intArray[nodeIndex]) {
         tmp = intArray[parentIndex];
         intArray[parentIndex] = intArray[nodeIndex];
         intArray[nodeIndex] = tmp;
         heapUp(parentIndex);
      }
   }
}
/**
* Heap down the root element being least in value, until heap property is broken. 
* Steps:
* 1.If current node has no children, done.  
* 2.If current node has one children and heap property is broken, 
* 3.Swap the current node and child node and heap down.
* 4.If current node has one children and heap property is broken, find smaller one
* 5.Swap the current node and child node and heap down.
* */
void heapDown(int nodeIndex){
   int leftChildIndex, rightChildIndex, minIndex, tmp;
   leftChildIndex = getLeftChildIndex(nodeIndex);
   rightChildIndex = getRightChildIndex(nodeIndex);
   if (rightChildIndex >= size) {
      if (leftChildIndex >= size)
         return;
      else
         minIndex = leftChildIndex;
   } else {
      if (intArray[leftChildIndex] <= intArray[rightChildIndex])
         minIndex = leftChildIndex;
      else
         minIndex = rightChildIndex;
   }
   if (intArray[nodeIndex] > intArray[minIndex]) {
      tmp = intArray[minIndex];
      intArray[minIndex] = intArray[nodeIndex];
      intArray[nodeIndex] = tmp;
      heapDown(minIndex);
   }
}
void insert(int value) {
   size++;
   intArray[size - 1] = value;
   heapUp(size - 1);
}
void removeMin() {
   intArray[0] = intArray[size - 1];
   size--;
   if (size > 0)
      heapDown(0);
}
int main() {
   /*                     5                //Level 0
   * 
   */
   insert(5);
   /*                     1                //Level 0
   *                     |
   *                 5---|                 //Level 1
   */   
   insert(1);
   /*                     1                //Level 0
   *                     |
   *                 5---|---3             //Level 1
   */
   insert(3);
   /*                     1                //Level 0
   *                     |
   *                 5---|---3             //Level 1
   *                 |
   *              8--|                     //Level 2
   */
   insert(8);
   /*                     1                //Level 0
   *                     |
   *                 5---|---3             //Level 1
   *                 |
   *              8--|--9                  //Level 2
   */
   insert(9);
   /*                     1                 //Level 0
   *                     |
   *                 5---|---3              //Level 1
   *                 |       |
   *              8--|--9 6--|              //Level 2
   */
   insert(6);
   /*                     1                 //Level 0
   *                     |
   *                 5---|---2              //Level 1
   *                 |       | 
   *              8--|--9 6--|--3           //Level 2
   */
   insert(2);

   printf("%d", getMinimum());

   removeMin();
   /*                     2                 //Level 0
   *                     |
   *                 5---|---3              //Level 1
   *                 |       |
   *              8--|--9 6--|              //Level 2
   */
   printf("\n%d", getMinimum());   
}
// 1
// 2

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

    def parent(self, i):
        return (i - 1) // 2

    def left_child(self, i):
        return 2 * i + 1

    def right_child(self, i):
        return 2 * i + 2

    def insert(self, val):
        self.heap.append(val)
        self.heapify_up(len(self.heap) - 1)

    def heapify_up(self, i):
        while i > 0 and self.heap[i] < self.heap[self.parent(i)]:
            # swap with heap.parent
            self.heap[i], self.heap[self.parent(i)] = self.heap[self.parent(i)], self.heap[i]
            i = self.parent(i)

    def pop_min(self):
        if len(self.heap) == 0:
            return None
        if len(self.heap) == 1:
            return self.heap.pop()

        min_val = self.heap[0]
        self.heap[0] = self.heap.pop()
        self.heapify_down(0)
        return min_val

    def heapify_down(self, i):
        while (left := self.left_child(i)) < len(self.heap):
            min_child = left
            right = self.right_child(i)
            if right < len(self.heap) and self.heap[right] < self.heap[left]:
                min_child = right
            if self.heap[i] <= self.heap[min_child]:
                # min heap
                break
            # swap this (parent) node with its min child node
            self.heap[i], self.heap[min_child] = self.heap[min_child], self.heap[i]
            i = min_child  # heapify again as the root node of the subtree


# Example
heap = Heap()
heap.insert(5)
heap.insert(1)
heap.insert(3)
heap.insert(8)
heap.insert(9)
heap.insert(6)
heap.insert(2)

print("Heap after insertion:", heap.heap)

min_element = heap.pop_min()
print("Min element popped:", min_element)

print("Heap after insertion:", heap.heap)

min_element = heap.pop_min()
print("Min element popped:", min_element)
print("Heap after popping:", heap.heap)
# Heap after insertion: [1, 5, 2, 8, 9, 6, 3]
# Min element popped: 1
# Heap after insertion: [2, 5, 3, 8, 9, 6]
# Min element popped: 2
# Heap after popping: [3, 5, 6, 8, 9]