Heap

Implementations

C++

#include <cstddef>
#include <vector>
 
template <typename T, typename Cmp = std::less<T>> class Heap {
  private:
	std::vector<T> array_;
	Cmp comp_;
 
	// INFO: you don't need a size
	// INFO: it's complete b tree in the sense that you FILL the
	// row for given height by virtue of the indexing being used
 
	// WARN:
	// the comp is strict weak ordered so a < b
	// doing a !comp(a, b) where invariant is that a < b
	// and thinking that it reads as if invariant does not hold
	// is wrong as it'll swap equals
	// read it instead as, if the invariant is in the other direction
	// then you swap
 
	inline std::size_t parent(std::size_t i) const { return (i - 1) >> 1; }
	inline std::size_t left(std::size_t i) const { return (i << 1) + 1; }
	inline std::size_t right(std::size_t i) const { return (i << 1) + 2; }
 
	void sift_up(std::size_t i) {
		// from i go all the way up while invariant does not hold
		// NOTE: comp being true is the invariant
		// say for min heapt comp gives true for a < b
		while (i > 0 && comp_(array_[i], array_[parent(i)])) {
			std::swap(array_[parent(i)], array_[i]);
			i = parent(i);
		}
	}
 
	void sift_down(std::size_t i) {
		// there's cur i and it's two children
		// invariant is that i must be smaller than both children
		// basically smallest of the 3, so we pick if the smaller child
		// if cur is not alreayd the smallest ( exit if that is the case )
		// and then swap to make the smallest of the 3 the cur
		while (i < array_.size()) {
			auto smallest = i;
			auto l = left(i);
			auto r = right(i);
			// read as => invariant should be comp_(smallest, l)
			// so if NOT of invariant, if the smallest is not the smallest
 
			for (auto child_pos : {l, r}) {
				if (child_pos < array_.size() &&
				    comp_(array_[child_pos], array_[smallest])) {
					smallest = child_pos;
				}
			}
 
			if (smallest == i)
				break;
			std::swap(array_[smallest], array_[i]);
			i = smallest;
		}
	}
 
  public:
	// no need of ctors or detors, custom ones will do
	// only the swaps mainain the invariant and since we push to some
	// position and then move the way up only the onces encountered
	// on the chain can possibly be wrong, for the rest the invariant
	// holds
	Heap() = default;
 
	Heap(const std::vector<T> &array) : array_(array) {
		// how to know the boundary? the first leaf will have no child sp
		// 2i+1 >=n
		// i >= (n-1)/2, by int division this is same as >= n/2
		for (std::size_t i = array_.size() / 2; i-- > 0;)
			sift_down(i);
		// NOTE:
		// we do in reverse form n/2 to 1 (inc) as
		// - n/2 beyond are all leaves so nothing to sift down to
		// - 0 is to top and assumes that sub-trees are heaps hence reverse
		// to go bottom up
		// How O(n)?
		// n/2 = 0 moves
		// n/4 => 1 moves ( worst case )
		// n/8 => 2
		// so n * (1/4 + 2/8 + 3/16) => this is a convergent series ( nums i
		// ari, denom is geo ) so n * constant
	}
 
	std::size_t size() const { return array_.size(); }
 
	const T &top() const {
		// must be const to preserve invariant
		return array_.front();
	}
 
	void push(const T &value) {
		array_.push_back(value);
		sift_up(array_.size() - 1);
	}
 
	void pop() {
		// 0 idx to be removed, so move it to back and just pop back
		std::swap(array_.front(), array_.back());
		array_.pop_back();
		sift_down(0); // this'll handle internally if empty
	}
};
 
int main() {
	Heap<int> heap;
	heap.push(10);
	heap.pop();
}

Java

import java.util.ArrayList;
import java.util.Collections;
 
final class Heap<T extends Comparable<? super T>> {
    private ArrayList<T> array = new ArrayList<T>();
 
    private int left(int i) {
        return 2 * i + 1;
    }
 
    private int right(int i) {
        return 2 * i + 2;
    }
 
    private int par(int i) {
        return (i - 1) / 2;
    }
 
    private void siftUp(int i) {
        // WARN: rem to do "if the invariant holds in the other direction"
        // doesn't really matter for java since I have the != info as well
        // but better to use ONE style
        while (i > 0 && array.get(i).compareTo(array.get(par(i))) < 0) {
            Collections.swap(array, i, par(i));
            i = par(i);
        }
    }
 
    private void siftDown(int i) {
        while (i < array.size()) {
            int smallest = i;
            int l = left(i);
            int r = right(i);
            // NOTE: avoid this, needless stack allocation
            // for(int childPos : [left(i), right(i)]){
 
            if (l < array.size() && array.get(l).compareTo(array.get(smallest)) < 0) {
                smallest = l;
            }
 
            // WARN: rem to compare to "smallest" and not i
            if (r < array.size() && array.get(r).compareTo(array.get(smallest)) < 0) {
                smallest = r;
            }
 
            if (smallest == i)
                break;
 
            Collections.swap(array, i, smallest);
            i = smallest;
        }
    }
 
    public int size() {
        return array.size();
    }
 
    // need offer = insert, peek = top and poll = remove and ret
    public void offer(T val) {
        array.add(val);
        siftUp(array.size() - 1);
    }
 
    public T peek() {
        return array.get(0);
    }
 
    public T poll() {
        Collections.swap(array, 0, array.size() - 1);
        var ret = array.removeLast();
        siftDown(0);
        return ret;
    }
}

Notes

cpp

what is std::less?

template <typename T>
struct less {
  bool operator()(const T& a, const T& b) const {
      return a < b;
  }
};

a struct that defines this operator() ( or class );

the std::sort needs a strict weak ordering means a < b and a < a is ALWAYS false ( the last part is what the strict is )

the func returns where it’s true if a is ”<” b by strick weak ordering