umma.dev

Algorithms + Data Structure: Heaps

🎨 Front End

9 min read

Delving into Heaps as part of the Algorithms and Data Structures series. Like the other posts, this post follows a similar format with explanations and problem sets at the end.

What is a Heap?

A heap has a tree-like structure, all heaps must be compelete binary trees. It is used to get the highest priority element at any point in time.

All heaps start with an index of one and the first index of zero in the array will always be null.

[index]

left child: i * 2
right child: i * 2 + 1
parent: i / 2

Min Heap

The parent node is always less than the child node.

class MinHeap() {
  let heap = [null]

  insert(num){
    heap.push(num)
    if(heap.length > 2) {
      let idx = heap.length - 1
      while(heap[idx] < heap[Math.floor(idx/2)]) {
        if(idx >= 1) {
          [heap[Math.floor(idx/2)], heap[idx]] = [heap[idx], heap[Math.floor(idx/2)]]
          if(Math.floor(idx/2) > 1) {
            idx = Math.floor(idx/2)
          } else {
            break
          }
        }
      }
    }
  }

  remove() {
    let smallest = heap[1]
    if(heap.length > 2) {
      heap[1] = heap[heap.length - 1]
      heap.splice(heap.length - 2)
      if(heap.length == 3) {
        if(heap[1] > heap[2]) {
          [heap[1], heap[2]] = [heap[2], heap[1]]
        }
        return smallest
      }
      let i = 1
      let left = 2 * i
      let right = 2 * i + 1
      while(heap[i] >= heap[left] || heap[i] >= heap[right]) {
        if(heap[left] < heap[right]) {
          [heap[i], heap[left]] = [heap[left], heap[i]]
          i = 2 * i
        } else {
          [heap[i], haep[right]] = [heap[right], heap[i]]
          i = 2 * i + 1
        }
        left = 2 * i
        right = 2 * i + 1
        if(heap[left] === undefined || heap[right] == undefined) {
          break;
        }
      }
      else if (heap.length == 2) {
        heap.splice(1, 1)
      } else {
        return null
      }
      return smallest
    }

    smallest() {
      let result = new Array()
      while(heap.length > 1) {
        result.push(this.remove())
      }
      return result
    }
  }
}

Max Heap

The parent node is always greater than or equal to the child node.

class MaxHeap() {
  let heap = [null]

  insert(num) {
    heap.push(num)
    if(heap.length > 2) {
      let idx = heap.length - 1
      while(heap[idx] > heap[Math.floor(idx/2)]) {
        if(idx >= 1) {
          [heap[Math.floor(idx/2)]. heap[idx]] = [heap[idx], heap[Math.floor(idx/2)]]
          if(Math.floor(idx/2) > 1) {
            idx = Math.floor(idx/2)
          } else {
            break
          }
        }
      }
    }
  }

  remove() {
    let smallest = heap[1]
    if(heap.length > 2) {
      heap[1] = heap[heap.length - 1]
      heap.splice(heap.length - 1)
      if(heap.length == 3) {
        if(heap[1] < heap[2]) {
          [heap[1], heap[2]] = [heap[2], heap[1]]
        }
        return smallest
      }
      let i = 1
      let left = 2 * i
      let right = 2 * i + 1
      while(head[i] <= heap[left] || heap[i] <= heap[right]) {
        if(heap[left] > heap[right]) {
          [heap[i], heap[left]] = [heap[left], heap[i]]
          i = 2 * i
        } else {
          [heap[i], heap[right]] = [heap[right], heap[i]]
          i = 2 * i + 1
        }
        left = 2 * i
        right = 2 * i + 1
        if(heap[left] == undefined || heap[right] == undefined) {
          break
        }
      }
      else if (heap.length == 2) {
        heap.splice(1, 1)
      }  else {
        return null
      }
      return smallest
    }
  }
}

Binary Heaps

This is an efficient way of implementing priority queues.

What’s a Priority Queue?

Essentially it’s a queue data structure with some additional properties. Every item has a priority associated with it (usually an integer). An item with a high priority is dequeued before an item with a low priority. Two items with an equal priority are dequeued based on their order in the queue. Priority rather than order - the tree is required to be complete and ordered.

class PriorityQueue {
  constructor() {
    this.heap = [null];
  }

  insert(value, priority) {
    const newNode = new Node(value, priority);
    this.heap.push(newNode);
    let currendNodeIdx = this.heap.length - 1;
    let currentNodeParentIdx = Math.floor(currentNodeIdx / 2);
    while (
      this.heap[currentNodeParentIdx] &&
      newNode.priority > this.heap[currentNodeParentIdx].priority
    ) {
      const parent = this.heap[currentNodeParentIdx];
      this.heap[currentNodeParentIdx] = newNode;
      this.heap[currentNodeIdx] = parent;
      currentNodeIdx = currentNodeParentIdx;
      currentNodeParentIdx = Math.floor(currentNodeIdx / 2);
    }
  }

  remove() {
    if (this.heap.length < 3) {
      const toReutrn = this.heap.pop();
      this.heap[0] = null;
      return toReturn;
    }
    const toReutrn = this.heap[1];
    this.heap[1] = this.heap.pop();
    let currentIdx = 1;
    left[(left, right)] = [2 * currentIdx, 2 * currentIdx + 1];
    let currentChildIdx =
      this.heap[right] && this.heap[right].priority >= this.heap[left].priority
        ? left
        : right;
    while (
      this.head[currentchildIdx] &&
      this.heap[currentIdx].priority <= this.heap[currentchildIdx].priority
    ) {
      let currentNode = this.heap[currentIdx];
      let currentChildNode = this.heap[currentChildIdx];
      this.heap[currentChildIdx] = currentNode;
      this.heap[currentIdx] = currentChildNode;
    }
    return toRemove;
  }
}

The Top K Problem

To implement you need to construct a min max heap, add all the elements into it, traversing and deleting the top element (storing it in an array) and repeating until you have removed K largest elements.

function firstKElements(arr, size, k) {
  let minHeap = [];

  for (let i = 0; i < k; i++) {
    minHeap.push(arr[i]);
  }

  for (let i = k; i < size; i++) {
    minHeap.sort((a, b) => a - b);
    if (minHeap[minHeap.length - 3] > arr[i]) {
      continue;
    } else {
      minHeap.reverse();
      minHeap.pop();
      minHeap.reverse();
      minHeap.push(arr[i]);
    }
  }
}

O-Notation

Access the min/max value: O(1)

Inserting an element: O(log n)

Removing an element: O(log n)

Problem Sets

Medium

Min Heap Construction

Implement a MinHeap class that supports:

  • Building a MinHeap from an input integers
  • Inserting integers at the heap
  • Removing the heap’s min/root value
  • Peeking at the heap’s min/root value
  • Sifting integers up and down the heap, which is to be used when inserting and removing values

Sample Input/Output

array = [48, 12, 24, 7, 8, -5, 24, 391, 24, 56, 2, 6, 8, 41]

minHeap(array) // instantiate a minheap (calls the buildHeap mehtod and populates the heap)
buildHeap(array) // [-5, 2, 6, 7, 8, 24, 391, 24, 56, 12, 24, 48, 41]
insert(76) // [-5, 2, 6, 7, 8, 24, 391, 24, 56, 12, 24, 48, 41, 76]
peek():
remove()

Code Given

class MinHeap {
  constructor(array) {
    this.heap = this.buildHeap(array);
  }

  buildHeap(array) {}

  siftDown() {}

  siftUp() {}

  peek() {}

  remove() {}

  insert(value) {}
}

Answer

class MinHeap {
  constructor(array) {
    this.heap = this.buildHeap(array);
  }

  buildHeap(array) {
    const parentIndex = Math.floor((array.length - 2) / 2);
    for (let i = parentIndex; i >= 0; i--) {
      this.siftDown(i, array.length - 1, array);
    }
    return array;
  }

  siftDown(currIndex, endIndex, heap) {
    let childIndex = currIndex * 2 + 1;
    while (childIndex <= endIndex) {
      const childTwoIndex =
        currIndex * 2 + 1 <= endIndex ? currIndex * 2 + 2 : -1;
      let indexSwap;
      if (childTwoIndex !== -1 && heap[childTwoIndex] < heap[childIndex]) {
        indexSwap = childTwoIndex;
      } else {
        indexSwap = childIndex;
      }
      if (heap[indexSwap] < heap[currIndex]) {
        this.swap(currIndex, indexSwap, heap);
        currIndex = indexSwap;
        childIndex = currIndex * 2 + 1;
      } else {
        return;
      }
    }
  }

  siftUp(currIndex, heap) {
    let parentIndex = Math.floor((currIndex - 1) / 2);
    while (currIndex > 0 && heap[currIndex] < heap[parentIndex]) {
      this.swap(currIndex, parentIndex, heap);
      currIndex = parentIndex;
      parentIndex = Math.floor((currIndex - 1) / 2);
    }
  }

  peek() {
    return this.heap[0];
  }

  remove() {
    this.swap(0, this.heap.length - 1, this.heap);
    const valRemove = this.heap.pop();
    this.siftDown(0, this.heap.length - 1, this.heap);
    return valRemove;
  }

  insert(value) {
    this.heap.push(value);
    this.siftUp(this.heap.length - 1, this.heap);
  }

  swap(i, j, heap) {
    const temp = heap[j];
    heap[j] = heap[i];
    heap[i] = temp;
  }
}

Hard

Sort K-sorted Array

Write a function that takes in a non-negative integer k and a k-sorted array of integers and returns the sorted version of the array. Your function can either sort the array in place or create an entirely new array.

A k-sorted array is a partially sorted array in which all elements are at most k positions away from their sorted position. For example the array [3, 1, 2, 2] is k-sorted with k=3, because each element in the array is at most 3 positions from its sorted position.

Sample Input

array = [3, 2, 1, 5, 4, 7, 6, 5]
k = 3

Sample Output

[1, 2, 3, 4, 5, 5, 6, 7]

Code Given

function sortKSortedArray(array, k) {
  return [];
}

Answer

function sortKSortedArray(array, k) {
  for (let i = 0; i < array.length; i++) {
    let j = i;
    let m = i + k;

    if (m <= array.length - 1) {
      let min = array[i];
      let indexOfi = i;
      while (j <= m) {
        if (array[j] <= min) {
          min = array[j];
          indexOfi = j;
        }
        j++;
      }
      // sliding window
      [array[i], array[indexOfi]] = [array[indexOfi], array[i]];
    } else {
      let remaining = [...array.slice(i, array.length)];
      let min = array[j];
      let indexOfj = j;
      let n = 0;
      while (n < remaining.length) {
        if (remaining[n] < min) {
          min = remaining[n];
          indexOfj = j + n;
        }
        n++;
      }
      [array[i], array[indexOfj]] = [array[indexOfj], array[i]];
    }
  }
  return array;
}

Very Hard

Merge Sorted Arrays

Write a function that takes in a non-empty sorted arraysof integers and returns a merged list of all those arrays. The integers in the merged list should be in sorted order.

Sample Input

array = [
  [1, 5, 9, 21],
  [-1, 0],
  [-124, 81, 121],
  [3, 6, 12, 20, 150]
]

Sample Output

[-124, -1, 0, 1, 3, 5, 6, 9, 12, 20, 21, 81, 121, 150]

Code Given

function mergeSortedArrays(arrays) {}

Answer

function mergeSortedArrays(arrays) {
  const sortedList = []
  const smallestItems = []
  for(let arrayIdx = 0; arrayIdx < arrays.length; arrayIdx++) {
    smallestItems.push({
      arrayIdx,
      elementIdx: 0,
      num: arrays[arrayIdx][0]
    })
  }

  const minHeap = new MinHeap(smallestItems)
  while(!minHeap.isEmpty()) {
    const smallestItem = minHeap.remove()
    const {arrayIdx, elementIdx, num} = smallestItem
    sortedList.push(num)
    if(elementIdx === arrays[arrayIdx].length - 1) continue
    minHeap.insert({
      arrayIdx,
      elementIdx: elementIdx + 1,
      num: arrays[arrayIdx][elementIdx + 1]
    })
  }
  return sortedList
}

class MinHeap {
  constructor(array) {
    this.heap = this.buildHeap(array)
  }

  isEmpty() {
    return this.heap.length === 0
  }

  buildHeap(array) {
    const firstParentIdx = Math.floor((array.length - 2)/2)
    for(let currentIdx = firstParentIdx; currentIdx >=0; currentIdx--) {
      this.siftDown(currentIdx, array.length - 1, array)
    }
    return array
  }

  siftDown(currentIdx, endIdx, heap) {
    left ChildOneIdx = currentIdx * 2 + 1
    while(childOneIdx <= endIdx) {
      const childTwoIdx = currentIdx * 2 + 2 <= endIdx ? currentIdx + 2 + 1 : -1
      let IdxToSwap
      if(childTwoIdx !== -1 && heap[childTwoIdx].num < heap[childOneIdx].num) {
        idxToSwap = childTwoIdx
      } else {
        idxtoSwap = childOneIdx
      }
      if(heap[inxToSwap].num < heap[currentIdx].num) {
        this.swap(currentIdx, idxToSwap, heap)
        currentIdx = idxToSwap
        childOneIdx = currentIdx * 2 + 1
      } else {
        return
      }
    }
  }

  siftUp(currentIdx, heap) {
    let parentIdx = Math.floor((currentIdx - 1)/2)
    while(currentIdx > 0 && heap[currentIdx].num < heap[parentIdx].num) {
      this.swap(currentIdx, parentIdx, heap)
      currentIdx = parentIdx
      parentIdx = Math.floor((currentIdx - 1)/2)
    }
  }

  remove() {
    this.swap(0, this.heap.length - 1, this.heap)
    const valuetoRemove = this.heap.pop()
    this.siftDown(0, this.heap.length - 1, this.heap)
    return valueToRemove
  }

  insert(value) {
    this.heap.push(value)
    this.siftUp(this.heap.length - 1, this.heap)
  }

  swap(i, j, heap) {
    const temp = heap[j]
    heap[j] = heap[i]
    heap[i] = temp
  }
}