Heap

Operation	find MIN/MAX	delete MIN/MAX - remove root node	insert - update a key	increase key	meld - merge 2 heaps
Binary	`O(1)`	`O(log n)`	`O(log n)`	`O(log n)`	`O(n)`
Leftist	`O(1)`	`O(log n)`	`O(log n)`	`O(log n)`	`O(log n)`
Binomial	`O(1)`	`O(log n)`	`O(1)`	`O(log n)`	`O(log n)`
Fibonacci	`O(1)`	`O(log n)`	`O(1)`	`O(1)`	`O(1)`
Pairing	`O(1)`	`O(log n)`	`O(1)`	`O(log n)`	`O(1)`
Brodal	`O(1)`	`O(log n)`	`O(1)`	`O(1)`	`O(1)`
Rank-pairing	`O(1)`	`O(log n)`	`O(1)`	`O(1)`	`O(1)`
Strict Fibonacci	`O(1)`	`O(log n)`	`O(1)`	`O(1)`	`O(1)`
2-3 heap	`O(log n)`	`O(log n)`	`O(log n)`	`O(1)`	`O(log n)`

Definition

Short
Detailed

Heap is a tree-like data structure used for efficient storage and retrieval of data.

Simplified

Heap, it's like a family tree of blocks where each block (called 'nodes') has children, but the rule is, the parent block is always bigger (or smaller depending on the type of heap) than its children blocks. This helps find the biggest or smallest block quickly.

Practice

Practice
Solution

Aspect	Pseudo Code
Heapify Up	`heapify_up(index): current_index = index current_element = heap[current_index] while current_index > 0: parent_index = (current_index - 1) / 2 parent = heap[parent_index] if current_element > parent: break heap[current_index] = parent current_index = parent_index heap[current_index] = current_element`
Heapify Down	heapify_down(index): current_index = index while current_index < heap.length: left_child_index=2 * current_index + 1 right_child_index = 2 * current_index + 2 left_child = heap[left_child_index] right_child = heap[right_child_index] min_child_index = ø if left_child == ø \|\| right_child == ø: if left_child == ø: min_child_index = left_child_index else: min_child_index = right_child_index else: if left_child == right_child: if left_child < heap[current_index]: min_child_index = left_child_index else: min_child_index = right_child_index else if left_child < heap[current_index]: min_child_index = left_child_index else: min_child_index = right_child_index if min_child_index == ø \|\| heap[min_child_index] > heap[current_index]: break min_child = heap[min_child_index] heap[current_index] = min_child current_index = min_child_index
Find MIN	`find_min(): if heap == ø: return ø return heap[0]`
Find MAX	`find_max(): if heap == ø: return ø return heap[heap.length - 1]`
Extract MIN	`extract_min(): if heap == ø: return ø min = heap[0] heap[0] = heap[heap.length - 1] heap.remove_last() heapify_down(0) return min`
Extract MAX	`extract_max(): if heap == ø: return ø max = heap[heap.length - 1] heap[0] = heap[heap.length - 1] heap.remove_last() heapify_down() return max`
Insertion	`insert(element): heap.add(element) heapify_up(heap.length - 1)`
Increase Key	`increase_key(index, newKey): if newKey <> heap[index]: "New key must be greater than current key" heap[index] = newKey heapifyUp(index)`
Decrease Key	`decrease_key(index, newKey): if newKey > heap[index]: "New key must be less than current key" heap[index] = newKey heapify_down(index)`
Meld	`meld(other): merged_heap = Heap() merged_heap.heap = heap + other.heap for i, i in heap.length / 2, i >= 0: heapify_down(i) return merged_heap`

package main

type Heap struct {
	comparator func(a, b interface{}) int
	heap       []interface{}
}

func NewHeap(comparator func(a, b interface{}) int) *Heap {
	return &Heap{
		comparator: comparator,
		heap:       []interface{}{},
	}
}

func (h *Heap) FindMin() interface{} {
	if len(h.heap) == 0 {
		return nil
	}
	return h.heap[0]
}

func (h *Heap) FindMax() interface{} {
	if len(h.heap) == 0 {
		return nil
	}
	return h.heap[len(h.heap)-1]
}

func (h *Heap) ExtractMin() interface{} {
	if len(h.heap) == 0 {
		return nil
	}

	min := h.heap[0]
	h.heap[0] = h.heap[len(h.heap)-1]
	h.heap = h.heap[:len(h.heap)-1]
	h.heapifyDown()

	return min
}

func (h *Heap) ExtractMax() interface{} {
	if len(h.heap) == 0 {
		return nil
	}

	max := h.heap[len(h.heap)-1]
	h.heap[0] = h.heap[len(h.heap)-1]
	h.heap = h.heap[:len(h.heap)-1]
	h.heapifyDown()

	return max
}

func (h *Heap) Insert(element interface{}) {
	h.heap = append(h.heap, element)
	h.heapifyUp()
}

func (h *Heap) IncreaseKey(index int, newKey interface{}) {
	if h.comparator(newKey, h.heap[index]) <= 0 {
		panic("New key must be greater than current key")
	}

	h.heap[index] = newKey
	h.heapifyUp(index)
}

func (h *Heap) DecreaseKey(index int, newKey interface{}) {
	if h.comparator(newKey, h.heap[index]) >= 0 {
		panic("New key must be less than current key")
	}

	h.heap[index] = newKey
	h.heapifyDown(index)
}

func (h *Heap) Meld(other *Heap) *Heap {
	mergedHeap := NewHeap(h.comparator)
	mergedHeap.heap = append(mergedHeap.heap, h.heap...)
	mergedHeap.heap = append(mergedHeap.heap, other.heap...)

	for i := len(h.heap) / 2; i >= 0; i-- {
		mergedHeap.heapifyDown(i)
	}

	return mergedHeap
}

func (h *Heap) heapifyUp(index int) {
	if index == 0 {
		return
	}

	parentIndex := (index - 1) / 2
	currentElement := h.heap[index]

	for index > 0 && h.comparator(currentElement, h.heap[parentIndex]) < 0 {
		h.heap[index] = h.heap[parentIndex]
		index = parentIndex
		parentIndex = (index - 1) / 2
	}

	h.heap[index] = currentElement
}

func (h *Heap) heapifyDown(index int) {
	if index >= len(h.heap) {
		return
	}

	for index*2+1 < len(h.heap) {
    leftChildIndex := index*2 + 1
    rightChildIndex := index*2 + 2
    leftChild := h.heap[leftChildIndex]
    rightChild := h.heap[rightChildIndex]

    minChildIndex := leftChildIndex
    if rightChildIndex < len(h.heap) && h.comparator(rightChild, leftChild) < 0 {
      minChildIndex = rightChildIndex
    }

    if h.comparator(h.heap[minChildIndex], h.heap[index]) < 0 {
      break
    }

    h.heap[index] = h.heap[minChildIndex]
    index = minChildIndex
  }

  h.heap[index] = h.heap[len(h.heap)-1]
}

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Heap<T> {

  private final Comparator<T> comparator;
  private final List<T> heap;

  public Heap(Comparator<T> comparator) {
    this.comparator = comparator;
    this.heap = new ArrayList<>();
  }

  public T findMin() {
    if (heap.isEmpty()) {
      return null;
    }
    return heap.get(0);
  }

  public T findMax() {
    if (heap.isEmpty()) {
      return null;
    }
    return heap.get(heap.size() - 1);
  }

  public T extractMin() {
    if (heap.isEmpty()) {
      return null;
    }

    T min = heap.get(0);
    heap.set(0, heap.get(heap.size() - 1));
    heap.remove(heap.size() - 1);
    heapifyDown();

    return min;
  }

  public T extractMax() {
    if (heap.isEmpty()) {
      return null;
    }

    T max = heap.get(heap.size() - 1);
    heap.set(0, heap.get(heap.size() - 1));
    heap.remove(heap.size() - 1);
    heapifyDown();

    return max;
  }

  public void insert(T element) {
    heap.add(element);
    heapifyUp();
  }

  public void increaseKey(int index, T newKey) {
    if (comparator.compare(newKey, heap.get(index)) < 0) {
      throw new IllegalArgumentException("New key must be greater than current key");
    }

    heap.set(index, newKey);
    heapifyUp(index);
  }

  public void decreaseKey(int index, T newKey) {
    if (comparator.compare(newKey, heap.get(index)) > 0) {
      throw new IllegalArgumentException("New key must be less than current key");
    }

    heap.set(index, newKey);
    heapifyDown(index);
  }

  public Heap<T> meld(Heap<T> other) {
    Heap<T> mergedHeap = new Heap<>(comparator);
    mergedHeap.heap.addAll(heap);
    mergedHeap.heap.addAll(other.heap);

    for (int i = heap.size() / 2; i >= 0; i--) {
      mergedHeap.heapifyDown(i);
    }

    return mergedHeap;
  }

  private void heapifyUp(int index) {
    int currentIndex = index;
    T currentElement = heap.get(currentIndex);

    while (currentIndex > 0) {
      int parentIndex = (currentIndex - 1) / 2;
      T parent = heap.get(parentIndex);

      if (comparator.compare(currentElement, parent) >= 0) {
        break;
      }

      heap.set(currentIndex, parent);
      currentIndex = parentIndex;
    }

    heap.set(currentIndex, currentElement);
  }

  private void heapifyDown(int index) {
    int currentIndex = index;

    while (currentIndex < heap.size()) {
      int leftChildIndex = 2 * currentIndex + 1;
      int rightChildIndex = 2 * currentIndex + 2;
      T leftChild = heap.getOrNull(leftChildIndex);
      T rightChild = heap.getOrNull(rightChildIndex);

      int minChildIndex = getMinChildIndex(leftChildIndex, rightChildIndex, leftChild, rightChild);

      if (minChildIndex == -1 || comparator.compare(heap.get(minChildIndex), heap.get(currentIndex)) >= 0) {
        break;
      }

      T minChild = heap.get(minChildIndex);
      heap.set(currentIndex, minChild);
      currentIndex = minChildIndex;
    }

    heap.set(currentIndex, heap.get(index));
  }

  private int getMinChildIndex(int leftChildIndex, int rightChildIndex, T leftChild, T rightChild) {
    if (leftChild == null || rightChild == null) {
      return (leftChild == null) ? leftChildIndex : rightChildIndex;
    } else {
      int leftChildComparison = comparator.compare(leftChild, rightChild);
      if (leftChildComparison == 0) {
        return (comparator.compare(leftChild, heap.get(currentIndex)) <= 0) ? leftChildIndex : rightChildIndex;
      } else {
        return (leftChildComparison == -1) ? leftChildIndex : rightChildIndex;
      }
    }
  }
}

class Heap {
  constructor(comparator) {
    this.comparator = comparator;
    this.heap = [];
  }

  findMin() {
    return this.heap[0] || null;
  }

  findMax() {
    return this.heap[this.heap.length - 1] || null;
  }

  extractMin() {
    if (this.heap.length === 0) {
      return null;
    }

    const min = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.heapifyDown();

    return min;
  }

  extractMax() {
    if (this.heap.length === 0) {
      return null;
    }

    const max = this.heap.pop();
    this.heap[0] = this.heap[this.heap.length - 1];
    this.heapifyDown();

    return max;
  }

  insert(element) {
    this.heap.push(element);
    this.heapifyUp();
  }

  increaseKey(index, newKey) {
    if (this.comparator(newKey, this.heap[index]) < 0) {
      throw new Error("New key must be greater than current key");
    }

    this.heap[index] = newKey;
    this.heapifyUp(index);
  }

  decreaseKey(index, newKey) {
    if (this.comparator(newKey, this.heap[index]) > 0) {
      throw new Error("New key must be less than current key");
    }

    this.heap[index] = newKey;
    this.heapifyDown(index);
  }

  meld(other) {
    const mergedHeap = new Heap(this.comparator);
    mergedHeap.heap = mergedHeap.heap.concat(this.heap, other.heap);

    for (let i = this.heap.length / 2 - 1; i >= 0; i--) {
      mergedHeap.heapifyDown(i);
    }

    return mergedHeap;
  }

  heapifyUp(index = this.heap.length - 1) {
    let currentIndex = index;
    const currentElement = this.heap[currentIndex];

    while (currentIndex > 0) {
      const parentIndex = Math.floor((currentIndex - 1) / 2);
      const parent = this.heap[parentIndex];

      if (this.comparator(currentElement, parent) >= 0) {
        break;
      }

      this.heap[currentIndex] = parent;
      currentIndex = parentIndex;
    }

    this.heap[currentIndex] = currentElement;
  }

  heapifyDown(index = 0) {
    let currentIndex = index;

    while (currentIndex < this.heap.length) {
      const leftChildIndex = 2 * currentIndex + 1;
      const rightChildIndex = 2 * currentIndex + 2;
      const leftChild = this.heap[leftChildIndex];
      const rightChild = this.heap[rightChildIndex];

      const minChildIndex =
        leftChild == null || rightChild == null
          ? leftChild == null
            ? leftChildIndex
            : rightChildIndex
          : this.comparator(leftChild, rightChild) === -1
            ? leftChildIndex
            : rightChildIndex;

      if (
        minChildIndex == null ||
        this.comparator(this.heap[minChildIndex], this.heap[currentIndex]) >= 0
      ) {
        break;
      }

      const minChild = this.heap[minChildIndex];
      this.heap[currentIndex] = minChild;
      currentIndex = minChildIndex;
    }

    this.heap[currentIndex] = this.heap[index];
  }
}

class Heap<T>(private val comparator: (T, T) -> Int) {
    private val heap: MutableList<T> = mutableListOf()

    fun findMin(): T? = heap.firstOrNull()

    fun findMax(): T? = heap.lastOrNull()

    fun extractMin(): T? {
        if (heap.isEmpty()) return null

        val min = heap[0]
        heap[0] = heap.last()
        heap.removeAt(heap.lastIndex)
        heapifyDown()

        return min
    }

    fun extractMax(): T? {
        if (heap.isEmpty()) return null

        val max = heap.last()
        heap[0] = heap.first()
        heap.removeAt(heap.lastIndex)
        heapifyDown()

        return max
    }

    fun insert(element: T) {
        heap.add(element)
        heapifyUp()
    }

    fun increaseKey(index: Int, newKey: T) {
        if (newKey < heap[index]) throw IllegalArgumentException("New key must be greater than current key")

        heap[index] = newKey
        heapifyUp(index)
    }

    fun decreaseKey(index: Int, newKey: T) {
        if (newKey > heap[index]) throw IllegalArgumentException("New key must be less than current key")

        heap[index] = newKey
        heapifyDown(index)
    }

    fun meld(other: Heap<T>): Heap<T> {
        val mergedHeap = Heap(comparator)
        mergedHeap.heap.addAll(heap)
        mergedHeap.heap.addAll(other.heap)

        for (i in heap.size / 2 downTo 0) {
            heapifyDown(i)
        }

        return mergedHeap
    }

    private fun heapifyUp(index: Int = heap.size - 1) {
        var currentIndex = index
        val currentElement = heap[currentIndex]

        while (currentIndex > 0) {
            val parentIndex = (currentIndex - 1) / 2
            val parent = heap[parentIndex]

            if (comparator(currentElement, parent) >= 0) break

            heap[currentIndex] = parent
            currentIndex = parentIndex
        }

        heap[currentIndex] = currentElement
    }

    private fun heapifyDown(index: Int = 0) {
        var currentIndex = index

        while (currentIndex < heap.size) {
            val leftChildIndex = 2 * currentIndex + 1
            val rightChildIndex = 2 * currentIndex + 2
            val leftChild = heap.getOrNull(leftChildIndex)
            val rightChild = heap.getOrNull(rightChildIndex)

            val minChildIndex = if (leftChild == null || rightChild == null) {
                if (leftChild == null) leftChildIndex else rightChildIndex
            } else {
                when (comparator(leftChild, rightChild)) {
                    -1 -> leftChildIndex
                    1 -> rightChildIndex
                    else -> if (comparator(leftChild, heap[currentIndex]) <= 0) leftChildIndex else rightChildIndex
                }
            }

            if (minChildIndex == null || comparator(heap[minChildIndex], heap[currentIndex]) >= 0) break

            val minChild = heap[minChildIndex]
            heap[currentIndex] = minChild
            currentIndex = minChildIndex
        }

        heap[currentIndex] = heap[index]
    }
}

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

    def find_min(self):
        if not self.heap:
            return None
        return self.heap[0]

    def find_max(self):
        if not self.heap:
            return None
        return self.heap[-1]

    def extract_min(self):
        if not self.heap:
            return None

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

        return min_val

    def extract_max(self):
        if not self.heap:
            return None

        max_val = self.heap[-1]
        self.heap[0] = self.heap[1]
        self.heap.pop()
        self.heapify_down()

        return max_val

    def insert(self, element):
        self.heap.append(element)
        self.heapify_up()

    def increase_key(self, index, new_key):
        if new_key < self.heap[index]:
            raise ValueError("New key must be greater than current key")

        self.heap[index] = new_key
        self.heapify_up(index)

    def decrease_key(self, index, new_key):
        if new_key > self.heap[index]:
            raise ValueError("New key must be less than current key")

        self.heap[index] = new_key
        self.heapify_down(index)

    def meld(self, other):
        merged_heap = Heap(self.comparator)
        merged_heap.heap = self.heap + other.heap

        for i in range(len(self.heap) // 2, -1, -1):
            merged_heap.heapify_down(i)

        return merged_heap

    def heapify_up(self, index=None):
        if index is None:
            index = len(self.heap) - 1
        current_index = index
        current_element = self.heap[current_index]

        while current_index > 0:
            parent_index = (current_index - 1) // 2
            parent = self.heap[parent_index]

            if self.comparator(current_element, parent) >= 0:
                break

            self.heap[current_index] = parent
            current_index = parent_index

        self.heap[current_index] = current_element

    def heapify_down(self, index=0):
        current_index = index

        while current_index < len(self.heap):
            left_child_index = 2 * current_index + 1
            right_child_index = 2 * current_index + 2
            left_child = self.heap[left_child_index] if left_child_index < len(self.heap) else None
            right_child = self.heap[right_child_index] if right_child_index < len(self.heap) else None

            min_child_index = left_child_index if left_child is None or (right_child is not None and self.comparator(left_child, right_child) <= 0) else right_child_index

            if min_child_index is None or self.comparator(self.heap[min_child_index], self.heap[current_index]) >= 0:
                break

            min_child = self.heap[min_child_index]
            self.heap[current_index] = min_child
            current_index = min_child_index

        self.heap[current_index] = self.heap[index]

struct Heap<T> {
    comparator: Box<dyn Fn(T, T) -> i32>,
    heap: Vec<T>,
}

impl<T> Heap<T> {
  fn new(comparator: Box<dyn Fn(T, T) -> i32>) -> Self {
      Heap {
          comparator,
          heap: vec![],
      }
  }

  fn find_min(&self) -> Option<&T> {
      self.heap.first()
  }

  fn find_max(&self) -> Option<&T> {
      self.heap.last()
  }

  fn extract_min(&mut self) -> Option<T> {
      if self.heap.is_empty() {
          return None;
      }

      let min = self.heap[0].clone();
      self.heap[0] = self.heap.pop().unwrap();
      self.heapify_down();

      Some(min)
  }

  fn extract_max(&mut self) -> Option<T> {
      if self.heap.is_empty() {
          return None;
      }

      let max = self.heap.pop().unwrap();
      self.heapify_down();

      Some(max)
  }

  fn insert(&mut self, element: T) {
      self.heap.push(element);
      self.heapify_up();
  }

  fn increase_key(&mut self, index: usize, new_key: T) {
      if (self.comparator)(&self.heap[index], &new_key) >= 0 {
          panic!("New key must be greater than current key");
      }

      self.heap[index] = new_key;
      self.heapify_up(index);
  }

  fn decrease_key(&mut self, index: usize, new_key: T) {
      if (self.comparator)(&self.heap[index], &new_key) <= 0 {
          panic!("New key must be less than current key");
      }

      self.heap[index] = new_key;
      self.heapify_down(index);
  }

  fn meld(&mut self, other: &mut Heap<T>) {
      let mut merged_heap = Heap::new(self.comparator.clone());
      merged_heap.heap.extend(self.heap.drain(..));
      merged_heap.heap.extend(other.heap.drain(..));

      for i in (merged_heap.heap.len() / 2)..0 {
          merged_heap.heapify_down(i);
      }

      *self = merged_heap;
  }

  fn heapify_up(&mut self, index: usize) {
      let mut current_index = index;
      let current_element = &mut self.heap[current_index];

      while current_index > 0 {
          let parent_index = (current_index - 1) / 2;
          let parent = &mut self.heap[parent_index];

          if (self.comparator)(current_element, parent) >= 0 {
              break;
          }

          std::mem::swap(current_element, parent);
          current_index = parent_index;
      }
  }

  fn heapify_down(&mut self, index: usize) {
      let mut current_index = index;

      while current_index < self.heap.len() {
          let left_child_index = 2 * current_index + 1;
          let right_child_index = 2 * current_index + 2;
          let left_child = self.heap.get(left_child_index);
          let right_child = self.heap.get(right_child_index);

          let min_child_index = if left_child.is_none() || right_child.is_none() {
              if left_child.is_none() {
                  right_child_index
              } else {
                  left_child_index
              }
          } else {
              let current_element = &self.heap[current_index];
              let left_child = left_child.unwrap();
              let right_child = right_child.unwrap();

              if (self.comparator)(current_element, left_child) <= 0
                  && (self.comparator)(current_element, right_child) <= 0
              {
                  return;
              }

              if (self.comparator)(left_child, right_child) <= 0 {
                  left_child_index
              } else {
                  right_child_index
              }
          };

          if (self.comparator)(&self.heap[min_child_index], &self.heap[current_index]) >= 0 {
              return;
          }

          self.heap.swap(current_index, min_child_index);
          current_index = min_child_index;
      }
  }
}

class Heap<T> {
  private comparator: (a: T, b: T) => number;
  private heap: T[];

  constructor(comparator: (a: T, b: T) => number) {
    this.comparator = comparator;
    this.heap = [];
  }

  findMin(): T | null {
    return this.heap[0] || null;
  }

  findMax(): T | null {
    return this.heap[this.heap.length - 1] || null;
  }

  extractMin(): T | null {
    if (this.heap.length === 0) return null;

    const min = this.heap[0];
    this.heap[0] = this.heap.pop() || null;
    this.heapifyDown();

    return min;
  }

  extractMax(): T | null {
    if (this.heap.length === 0) return null;

    const max = this.heap.pop();
    this.heapifyDown();

    return max;
  }

  insert(element: T) {
    this.heap.push(element);
    this.heapifyUp();
  }

  increaseKey(index: number, newKey: T) {
    if (this.comparator(newKey, this.heap[index]) < 0) {
      throw new Error("New key must be greater than current key");
    }

    this.heap[index] = newKey;
    this.heapifyUp(index);
  }

  decreaseKey(index: number, newKey: T) {
    if (this.comparator(newKey, this.heap[index]) > 0) {
      throw new Error("New key must be less than current key");
    }

    this.heap[index] = newKey;
    this.heapifyDown(index);
  }

  meld(other: Heap<T>): Heap<T> {
    const mergedHeap = new Heap<T>(this.comparator);
    mergedHeap.heap = mergedHeap.heap.concat(this.heap, other.heap);

    for (let i = mergedHeap.heap.length / 2 - 1; i >= 0; i--) {
      mergedHeap.heapifyDown(i);
    }

    return mergedHeap;
  }

  private heapifyUp(index: number = this.heap.length - 1) {
    let currentIndex = index;
    const currentElement = this.heap[currentIndex];

    while (currentIndex > 0) {
      const parentIndex = (currentIndex - 1) >> 1;
      const parent = this.heap[parentIndex];

      if (this.comparator(currentElement, parent) >= 0) break;

      this.heap[currentIndex] = parent;
      currentIndex = parentIndex;
    }

    this.heap[currentIndex] = currentElement;
  }

  private heapifyDown(index: number = 0) {
    let currentIndex = index;

    while (currentIndex < this.heap.length) {
      const leftChildIndex = currentIndex * 2 + 1;
      const rightChildIndex = currentIndex * 2 + 2;
      const leftChild = this.heap[leftChildIndex];
      const rightChild = this.heap[rightChildIndex];

      let minChildIndex: number | null = null;

      if (leftChild !== undefined && rightChild !== undefined) {
        if (this.comparator(leftChild, rightChild) <= 0) {
          minChildIndex = leftChildIndex;
        } else {
          minChildIndex = rightChildIndex;
        }
      } else if (leftChild !== undefined) {
        minChildIndex = leftChildIndex;
      } else if (rightChild !== undefined) {
        minChildIndex = rightChildIndex;
      }

      if (minChildIndex === null) {
        break;
      }

      const minChild = this.heap[minChildIndex];
      if (this.comparator(minChild, this.heap[currentIndex]) >= 0) {
        break;
      }

      this.heap[currentIndex] = minChild;
      this.heap[minChildIndex] = this.heap[currentIndex];
      currentIndex = minChildIndex;
    }

    this.heap[currentIndex] = this.heap[index];
  }
}

Definition​

Practice​

Definition

Practice