Tag Archives: binary

Counting inversions via rank queries

In a post from about a year ago, I explained an algorithm for counting the number of inversions of a sequence in time. As a reminder, given a sequence , an inversion is a pair of positions such that and … Continue reading

Posted in haskell | Tagged , , , , , , , , , | 4 Comments

Sum of heights in a binary tree

Executive summary: every year when teaching data structures I always forget how to analyze the cost of building a binary heap, which amounts to summing the heights of all the nodes in a full binary tree. So I’m writing down … Continue reading

Posted in math, teaching | Tagged , , , , , , , | 2 Comments