dheap.ts

interface DHeap {
  heap: number[];
  breadth: number;
}

export function buildDHeap(breadth: number): DHeap {
  return {
    heap: [],
    breadth,
  };
}

export function bulkInsert(dHeap: DHeap, nodes: number[]) {
  nodes.forEach((node) => {
    insert(dHeap, node);
  });
}

function insert(dHeap: DHeap, node: number) {
  let index = dHeap.heap.length;
  let parentIndex = getParentIndex(dHeap, index);

  while (index !== 0 && node < dHeap.heap[parentIndex]) {
    dHeap.heap[index] = dHeap.heap[parentIndex];
    index = parentIndex;
    parentIndex = getParentIndex(dHeap, index);
  }

  dHeap.heap[index] = node;
}

function getParentIndex(dHeap: DHeap, index: number) {
  return Math.floor((index - 1) / dHeap.breadth);
}

function getKthChildrenIndex(dHeap: DHeap, parentIndex: number, k: number) {
  return Math.floor(dHeap.breadth * parentIndex + k);
}

function getMinChildIndex(dHeap: DHeap, parentIndex: number) {
  const startIndex: number = getKthChildrenIndex(dHeap, parentIndex, 1);
  let minIndex = startIndex;
  for (let i = 0; i <= dHeap.breadth; i++) {
    if (dHeap.heap[minIndex] > dHeap.heap[startIndex + i]) {
      minIndex = startIndex + i;
    }
  }

  return minIndex;
}

function downHeap(dHeap: DHeap, parentIndex: number = 0) {
  const initialKValue = dHeap.heap[parentIndex];
  let minChildIndex = getMinChildIndex(dHeap, parentIndex);

  while (
    minChildIndex <= dHeap.heap.length &&
    initialKValue > dHeap.heap[minChildIndex]
  ) {
    dHeap.heap[parentIndex] = dHeap.heap[minChildIndex];
    parentIndex = minChildIndex;
    minChildIndex = getMinChildIndex(dHeap, parentIndex);
  }

  dHeap.heap[parentIndex] = initialKValue;
}

export function delMin(dHeap: DHeap) {
  dHeap.heap[0] = dHeap.heap.pop();
  downHeap(dHeap);
}

export function heapfy(dHeap: DHeap, nodes: number[]) {
  if (nodes.length === 0) {
    return;
  }

  dHeap.heap = nodes;

  let parentIndex = getParentIndex(dHeap, dHeap.heap.length - 1);
  while (parentIndex >= 0) {
    downHeap(dHeap, parentIndex);
    parentIndex--;
  }
}