Heapable Sequences and Subsequences

John W. Byers, Brent Heeringa, Michael Mitzenmacher, Georgios Zervas

This paper, authored by researchers from Boston University, Williams College, and Harvard, introduces a fascinating new twist on a classic combinatorial problem: the Longest Increasing Subsequence (LIS). By adding a hierarchical constraint, they define "heapable" sequences and explore the algorithmic and probabilistic boundaries of this new structure.

TL;DR

The authors introduce "heapable sequences"—numbers that can be inserted one by one into a binary tree while maintaining the heap property. They prove that while checking if a sequence can form any heap is easy, forcing it into a complete binary tree is NP-hard, and they show that for random data, nearly the entire sequence can be made heapable.

What Problem Does This Paper Address?

In computer science, the Longest Increasing Subsequence (LIS) problem is a cornerstone of combinatorics, with applications ranging from DNA sequencing to card sorting. This paper asks: what if instead of a simple line (an increasing sequence), we want to build a hierarchy?

The authors define a sequence as heapable if you can take the numbers in order and place them into a binary tree such that every parent is less than or equal to its children (the min-heap property). The catch is the "online" constraint: each new number must be placed as a leaf under an existing node.

This isn't just a mathematical curiosity; it models real-world scenarios like the "Secretary Problem" for organizations. Imagine hiring a team where every manager must be more qualified than their direct reports, and you must assign roles as candidates arrive.

Methods

The researchers tackle the problem from three angles:

  1. Algorithmic Complexity: They develop Greedy-Sig, an algorithm that determines if a sequence is heapable in $O(n \log n)$ time. It works by maintaining a "signature"—a sorted list of available slots (parent values) and greedily placing the current number under the largest possible parent that doesn't violate the heap property.
  2. Hardness Proofs: They use a reduction from the "Exact Cover by 3-Sets" problem to prove that determining if a sequence can form a complete binary heap (one with no gaps) is NP-hard.
  3. Probabilistic Analysis: For random permutations, they use "banding" techniques—restricting certain value ranges to specific levels of the tree—to prove lower bounds on how much of a random sequence can be "heaped."

Datasets

The paper does not use real-world datasets. Instead, it relies on:

  • Random Permutations: Theoretical models of $n$ numbers.
  • Monte Carlo Simulations: Used to investigate the scaling properties of heapable subsequences and to estimate the probability of a random sequence being heapable as $n$ grows.

Key Insights and Ideas

  • The Greedy Strategy is Optimal: For general heapability, a greedy approach (picking the largest available parent $\le$ the current value) is the best you can do. This is a powerful result because it simplifies the search space significantly.
  • Shape Matters: There is a massive gap in complexity between building any heap and building a complete heap. The requirement to fill every level of the tree perfectly makes the problem computationally "intractable" (NP-hard).
  • Heaps are "Roomy": In a standard LIS of a random permutation of length $n$, the expected length is only $2\sqrt{n}$. However, for a Longest Heapable Subsequence (LHS), the authors show you can capture $(1 - o(1))n$ elements. In other words, almost the entire random sequence can fit into a heap, whereas only a tiny fraction fits into a simple increasing line.
  • 0-1 Sequences are Special: While complete heapability is hard for general numbers, it becomes a linear-time problem if you only have two values (0s and 1s).

Key Results

  • Heapability Check: Can be done in $O(n \log n)$ generally, or $O(n \log \log n)$ using advanced data structures like van Emde Boas trees.
  • Random Data Performance: For a random permutation of size $n$, the Longest Heapable Subsequence has length nearly $n$ with high probability.
  • Complete Heaps in Random Data: Even with the strict "complete tree" constraint, you can still find a heapable subsequence of length $\alpha n$ (a constant fraction of the total) in random data.
  • Counter-intuitive Upper Bound: They proved the existence of "bad" sequences where the longest increasing or decreasing heapable subsequence is only $O(n / \log n)$, showing that some sequences are inherently resistant to hierarchical organization.

Limitations and Future Work

The authors leave several intriguing doors open:

  • The LHS Complexity: While they found an algorithm to check if a whole sequence is heapable, they haven't yet determined if finding the longest possible heapable subsequence is NP-hard.
  • Alphabet Size: They solved the 0-1 case and the general case; the complexity for "intermediate" alphabet sizes (e.g., a sequence of only 10 distinct values) remains unknown.
  • Refined Constants: The probabilistic results prove that the LHS is "nearly $n$," but the exact distribution and the constant factors involved in the $o(1)$ term are still up for grabs.
  • Hiring Models: Future work could incorporate more realistic hiring constraints, such as penalties for leaving "manager" positions unfilled for too long.

Summary updated

Abstract

Let us call a sequence of numbers heapable if they can be sequentially inserted to form a binary tree with the heap property where each insertion subsequent to the first occurs at a leaf of the tree, i.e. below a previously placed number. In this paper we consider a variety of problems related to heapable sequences and subsequences that do not appear to have been studied previously. Our motivation for introducing these concepts is two-fold. First, such problems correspond to natural extensions of the well-known secretary problem for hiring an organization with a hierarchical structure. Second, from a purely combinatorial perspective, our problems are interesting variations on similar longest increasing subsequence problems, a problem paradigm that has led to many deep mathematical connections. We provide several basic results. We obtain an efficient algorithm for determining the heapability of a sequence, and also prove that the question of whether a sequence can be arranged in a complete binary heap is NP-hard. Regarding subsequences we show that, with high probability, the longest heapable subsequence of a random permutation of n numbers has length (1 – o(1))n, and a subsequence of length (1 – o(1))n can in fact be found online with high probability. We similarly show that for a random permutation a subsequence that yields a complete heap of size αn for a constant α can be found with high probability. Our work highlights the interesting structure underlying this class of subsequence problems, and we leave many further interesting variations open for future work.
BibTeX
@inproceedings{byers2011heapable,
  author = {John W. Byers and Brent Heeringa and Michael Mitzenmacher and Georgios Zervas},
  title = {{Heapable Sequences and Subsequences}},
  booktitle = {ANALCO},
  year = {2011},
  url = {https://openreview.net/forum?id=GmfBf3Z_9hN},
}

Loading related content...

Figure