The heap is a type of data structure that represents a binary tree. They have a root element, left and right sub-tree, and children. A root element is the item at the top of the tree that branches out into other elements, similar to the root of an actual tree.

Example of a heap structure:

The roots of a tree:

There two main types of heap structures, min-max heaps, and max-min heaps.

Min-Max Heap

A min-max heap is a complete binary tree containing alternating even and odd levels. Even levels can be represented as 0, 2, and 4, and odd levels can be represented as 1, 3, 5, etc. In a min-max heap, the smallest value or minimum is at the root and each parent is less than or equal to its children while each parent in the max level is greater than its children. The root element is considered to be at the first level, i.e. 0.

Example of a min-max heap:

Example of a binary tree:

Main Features of Min-max Heap

This type of heap is typically characterized by the following:

1. Each node in a min-max heap is associated with a data member whose value is implemented to calculate the order of the node in the min-max heap. This is usually called key.
2. The root element should be the minimum element of the min-max heap.
3. One of the two elements in the second level, which is an odd level, is the maximum element in the min-max heap.
4. If y is a node in a min-max heap and y is on an even level, then the key of y should be the smallest key among all keys in the subtree with y as the root.
5. If the same y is on an odd level, then the key of y should be the highest among all the keys of a subtree with a root of y.
6. A Node on a min (max) level is denoted as a min (max) node.

Implementation

This is the Python implementation:

import math

class MinMaxHeap:
    def __init__(self):
        self.heap = []  # array-based representation

    def level(self, index):
        """Return level (0 = min, 1 = max, etc.)"""
        return int(math.log2(index + 1))

    def parent(self, index):
        return (index - 1) // 2 if index > 0 else None

    def children(self, index):
        """Return indices of children if they exist"""
        left, right = 2 * index + 1, 2 * index + 2
        return [i for i in (left, right) if i < len(self.heap)]

    def add(self, value):
        if not isinstance(value, int):
            raise Exception("Please insert a number")

        # Insert at the end
        self.heap.append(value)
        self._bubble_up(len(self.heap) - 1)

    def _bubble_up(self, index):
        """Bubble up according to min-max rules"""
        if index == 0:
            return

        level = self.level(index)
        parent = self.parent(index)

        if level % 2 == 0:  # min level
            if self.heap[index] > self.heap[parent]:
                # Swap with parent and bubble up in max level
                self.heap[index], self.heap[parent] = self.heap[parent], self.heap[index]
                self._bubble_up_max(parent)
            else:
                self._bubble_up_min(index)
        else:  # max level
            if self.heap[index] < self.heap[parent]:
                # Swap with parent and bubble up in min level
                self.heap[index], self.heap[parent] = self.heap[parent], self.heap[index]
                self._bubble_up_min(parent)
            else:
                self._bubble_up_max(index)

    def _bubble_up_min(self, index):
        grandparent = self.parent(self.parent(index)) if self.parent(index) is not None else None
        if grandparent is not None and self.heap[index] < self.heap[grandparent]:
            self.heap[index], self.heap[grandparent] = self.heap[grandparent], self.heap[index]
            self._bubble_up_min(grandparent)

    def _bubble_up_max(self, index):
        grandparent = self.parent(self.parent(index)) if self.parent(index) is not None else None
        if grandparent is not None and self.heap[index] > self.heap[grandparent]:
            self.heap[index], self.heap[grandparent] = self.heap[grandparent], self.heap[index]
            self._bubble_up_max(grandparent)

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

    def find_max(self):
        if len(self.heap) <= 1:
            return self.heap[0] if self.heap else None
        elif len(self.heap) == 2:
            return self.heap[1]
        else:
            return max(self.heap[1], self.heap[2])

    def __str__(self):
        return str(self.heap)


# Example usage
test_heap = MinMaxHeap()
test_heap.add(10)
test_heap.add(15)
test_heap.add(40)
test_heap.add(50)
test_heap.add(30)
test_heap.add(100)
test_heap.add(40)

print("Heap:", test_heap)
print("Min:", test_heap.find_min())
print("Max:", test_heap.find_max())
print("Children:", test_heap.children(1))

This is the JavaScript implementation:

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

  level(index) {
    // Returns level (0 = min, 1 = max, etc.)
    return Number(Math.log2(index + 1));
  }

  parent(index) {
    return Math.floor(index > 0) ? (index - 1) / 2 : null;
  }

  children(index) {
    // Return indices of children if they exist
    let left,
      right = 2 * index + 1;
    2 * index + 2;
    const output = [];
    if (left < this.heap.length) {
      output.push(left);
    }
    if (right < this.heap.length) {
      output.push(right);
    }
    return output;
  }

  add(value) {
    if (typeof value !== "number") {
      throw Error("Please insert a number");
    }

    // Insert at the end
    this.heap.push(value);
    this.bubbleUp(this.heap.length - 1);
  }

  bubbleUp(index) {
    // Bubble up according to min-max rules
    if (index === 0) return 0;

    const level = this.level(index);
    const parent = this.parent(index);

    // Min level
    if (level % 2 === 0) {
      if (this.heap[index] > this.heap[parent]) {
        // Swap with parent and bubble up in max level
        this.heap[index],
          (this.heap[parent] = this.heap[parent]),
          this.heap[index];
        this.bubbleUpMax(parent);
      } else {
        this.bubbleUpMin(index);
      }
      // Max level
    } else {
      if (this.heap[index] < this.heap[parent]) {
        // Swap with parent and bubble up in the min level
        this.heap[index],
          (this.heap[parent] = this.heap[parent]),
          this.heap[index];
        this.bubbleUpMin(parent);
      } else {
        this.bubbleUpMax(index);
      }
    }
  }

  bubbleUpMin(index) {
    let grandParent;
    if (this.parent(index) !== null) {
      grandParent = this.parent(this.parent(index));
    } else {
      grandParent = null;
    }

    if (grandParent !== null && this.heap[index] < this.heap[grandParent]) {
      this.heap[index],
        (this.heap[grandParent] = this.heap[grandParent]),
        this.heap[index];
      this.bubbleUpMin(grandParent);
    }
  }

  bubbleUpMax(index) {
    let grandParent;
    if (this.parent(index) !== null) {
      grandParent = this.parent(this.parent(index));
    } else {
      grandParent = null;
    }

    if (grandParent !== null && this.heap[index] > this.heap[grandParent]) {
      this.heap[index],
        (this.heap[grandParent] = this.heap[grandParent]),
        this.heap[index];
      this.bubbleUpMax(grandParent);
    }
  }

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

  findMax() {
    if (this.heap.length <= 1) {
      return this.heap[0] ? this.heap[0] : null;
    } else if (this.heap.length === 2) {
      return this.heap[1];
    } else {
      return Math.max(...this.heap);
    }
  }

  showHeap() {
    return this.heap;
  }
}

const testHeap = new MinMaxHeap();
testHeap.add(10);
testHeap.add(15);
testHeap.add(40);
testHeap.add(50);
testHeap.add(30);
testHeap.add(100);
testHeap.add(40);

console.log("Heap:", testHeap.showHeap());
console.log("Min:", testHeap.findMin());
console.log("Max:", testHeap.findMax());
console.log("Children:", testHeap.children(1));

Final Thoughts

Some key considerations are:

1. Using an array-based heap representation instead of objects.
2. Correct level detection and bubble up logic to enforce min/max at alternative levels.
3. Implementing functions for finding minimum and maximum.
4. Extendable for delete operations.

A Max-min heap is defined as the opposite to min-max heap. In such a heap, the highest value is stored at the root, and the minimum value is stored at one of the root's children. Feel free to try and implement a Max-min heap and share the results with me😁.

Until next time, happy coding.