Heap

Implement a heap data structure in JavaScript that supports the following operations:

new Heap(array): Creates an instance of a Heap class initialized with array and heapifies it to form as the initial Heap structure. It also initializes any internal structure needed to maintain the heap properties.
heapify(array): Constructs the heap from an unordered array, establishing the max heap property across all elements. This is performed as part of the constructor, or can be a separate method that resets and rebuilds the heap. Required time complexity: O(n), where n is the number of elements in the array.
insert(value): Adds a new value to the heap, maintaining the max heap property. Required time complexity: O(log n), where n is the number of elements in the heap after insertion.
delete(): Removes and returns the maximum value from the heap, maintaining the max heap property after removal. Required time complexity: O(log n).
findMax(): Returns the maximum value in the heap without removing it. Required time complexity: O(1).

Examples

const heap = new Heap();
heap.insert(20);
heap.insert(15);
heap.insert(30);
heap.findMax(); // 30
heap.insert(10);
heap.delete(); // 30
heap.findMax(); // 20

const array = [5, 3, 17, 10, 84, 19, 6, 22, 9];
const newHeap = new Heap(array);
newHeap.findMax(); // 84

Coding and submission is not supported on mobile devices. Use a wider screen to practice solving this question within the editor.

Heap

Implement a heap data structure in JavaScript that supports the following operations:

new Heap(array): Creates an instance of a Heap class initialized with array and heapifies it to form as the initial Heap structure. It also initializes any internal structure needed to maintain the heap properties.
heapify(array): Constructs the heap from an unordered array, establishing the max heap property across all elements. This is performed as part of the constructor, or can be a separate method that resets and rebuilds the heap. Required time complexity: O(n), where n is the number of elements in the array.
insert(value): Adds a new value to the heap, maintaining the max heap property. Required time complexity: O(log n), where n is the number of elements in the heap after insertion.
delete(): Removes and returns the maximum value from the heap, maintaining the max heap property after removal. Required time complexity: O(log n).
findMax(): Returns the maximum value in the heap without removing it. Required time complexity: O(1).

Examples

const heap = new Heap();
heap.insert(20);
heap.insert(15);
heap.insert(30);
heap.findMax(); // 30
heap.insert(10);
heap.delete(); // 30
heap.findMax(); // 20

const array = [5, 3, 17, 10, 84, 19, 6, 22, 9];
const newHeap = new Heap(array);
newHeap.findMax(); // 84

Solution

Heaps are specialized tree-based data structures that satisfy the heap property, where in a max heap, each parent node is greater than or equal to the values of its children. This property makes heaps ideal for implementing priority queues, where the highest (or lowest) priority element needs to be accessed quickly.

Operations

heapify(array): Constructs the heap from an unordered array. This is done by performing a series of insert operations from the bottom half of the array to build the heap in place.
insert(value): Adds a new element to a heap. This involves appending the element at the end of the array (which represents the heap) and then move up the newly added element until the heap property is restored if it's violated.

Insert

delete(): Removes the root element of the heap, which is the maximum value in a max heap. The last element of the heap replaces the root, and then slowly move it down until the heap property is restored.

Delete

findMax(): Returns the element at the root of the heap without removing it, providing constant time access to the maximum value.

Since the operations insert and delete can potentially involve moving elements across the height of the heap, their time complexity is O(log n), where n is the number of elements in the heap. findMax is a constant-time operation, O(1), as it returns the first element. Heapify has a time complexity of O(n log(n)) as it goes through each element and slowly inserting them one by one.

Edge Cases

Inserting into an empty heap.
Deleting from an empty heap.
Calling findMax on an empty heap.

Techniques

Object-oriented programming.
Array manipulation to simulate a binary tree.
Understanding of logarithmic time complexity and how operations can affect it.

This heap implementation focuses on efficient data manipulation, taking advantage of the properties of binary trees to ensure that high-priority items are quickly accessible while maintaining the ability to adjust in logarithmic time.

export default class Heap {
  constructor(array = []) {
    this.values = [];
    if (array.length > 0) {
      this.heapify(array);
    }
  }

  /**
   * Constructs the initial heap structure with a given `array`.
   * @param {Array} array The initial array.
   */
  heapify(array) {
    this.values = [];
    array.forEach((element) => this.insert(element));
  }

  /**
   * Adds an item into the heap.
   * @param {*} item The item to be added into the heap.
   */
  insert(value) {
    this.values.push(value);
    let index = this.values.length - 1;
    let parentIndex = Math.floor((index - 1) / 2);

    // Move up the newly added value until the heap property is restored.
    while (index > 0 && this.values[parentIndex] < this.values[index]) {
      [this.values[parentIndex], this.values[index]] = [
        this.values[index],
        this.values[parentIndex],
      ];
      index = parentIndex;
      parentIndex = Math.floor((index - 1) / 2);
    }
  }

  /**
   * Removes the top of the heap / maximum element.
   * @return {*} The element removed.
   */
  delete() {
    if (this.values.length === 0) {
      return undefined;
    }
    const max = this.values[0];
    const last = this.values.pop();
    if (this.values.length === 0) {
      return max;
    }

    this.values[0] = last;
    let index = 0;

    // Restore heap property by moving down the root value.
    while (true) {
      const left = 2 * index + 1;
      const right = 2 * index + 2;
      let largest = index;

      // If left child exists and is larger than the current largest, replace largest with value of left child.
      if (
        left < this.values.length &&
        this.values[left] > this.values[largest]
      ) {
        largest = left;
      }

      // If right child exists and is larger than the current largest, replace largest with value of right child.
      if (
        right < this.values.length &&
        this.values[right] > this.values[largest]
      ) {
        largest = right;
      }

      if (largest === index) {
        break; // The current root is already the largest, heap property is satisfied.
      }

      // Swap the position such that the largest value is above `index`, following the heap property.
      [this.values[index], this.values[largest]] = [
        this.values[largest],
        this.values[index],
      ];
      index = largest;
    }

    return max;
  }

  /**
   * Returns the value of the maximum element.
   * @return {number} The maximum element.
   */
  findMax() {
    return this.values.length > 0 ? this.values[0] : undefined;
  }
}

Heap

Examples

Heap

Examples

Similar questions

Solution

Operations

Edge Cases

Techniques

You must be signed in to view your submissions

Loading editor

Loading editor

Loading tests

JavaScript Console

Loading tests