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 \alpha n for a constant \alpha 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.
1. Introduction
The study of sequences and their properties is a fundamental area of combinatorics and computer science. One of the most well-known problems in this domain is the Longest Increasing Subsequence (LIS), which has wide-ranging applications from bioinformatics to sorting algorithms. This paper, authored by researchers from Boston University, Williams College, and Harvard, introduces a novel hierarchical extension to the LIS problem: "heapable" sequences.
2. Defining Heapability
A sequence of numbers is defined as heapable if its elements can be sequentially inserted into a binary tree such that the min-heap property is maintained—where every parent node is less than or equal to its children. Crucially, this process must follow an "online" constraint: each subsequent number must be placed as a leaf under a previously positioned node.
This concept is motivated by practical scenarios such as a hierarchical "Secretary Problem." In this model, an organization seeks to hire a team where managers must be more qualified than their subordinates, and roles must be assigned immediately as candidates arrive.
3. Algorithmic Complexity and Hardness
The researchers explore the computational limits of heapability through two primary lenses: general heapability and complete binary heaps.
General Heapability: The authors demonstrate that determining if a sequence is heapable is computationally efficient. They introduce Greedy-Sig, an algorithm that operates in $O(n \log n)$ time. The algorithm maintains a "signature"—a sorted list of available parent slots—and greedily assigns the current number to the largest possible parent that satisfies the heap property. This greedy strategy is proven to be optimal for general heapability.
Complete Binary Heaps: In contrast, the problem becomes significantly more difficult when the resulting tree must be a complete binary tree (one with no gaps). The authors prove that determining if a sequence can form a complete binary heap is NP-hard, using a reduction from the "Exact Cover by 3-Sets" problem. This highlights a stark complexity gap between building any hierarchical structure and building a perfectly balanced one.
4. Probabilistic Analysis of Random Permutations
A major contribution of the paper is the analysis of heapable subsequences within random permutations of $n$ numbers. While the expected length of an LIS in a random permutation is $2\sqrt{n}$, the authors show that heaps are far more "roomy."
Specifically, they prove that for a random permutation, the Longest Heapable Subsequence (LHS) has a length of $(1 - o(1))n$ with high probability. This means that almost the entire sequence can be organized into a hierarchy. To prove these lower bounds, the authors employ "banding" techniques, which involve restricting specific ranges of values to certain levels or regions of the tree.
Even under the stricter constraint of forming a complete binary heap, the authors show that a subsequence of length $\alpha n$ (for some constant $\alpha$) can be found with high probability in random data.
5. Conclusion and Future Directions
This work establishes the foundational theory for heapable sequences, revealing a rich structure that differs significantly from traditional linear subsequences. While general heapability is easily checked, many questions remain. For instance, the complexity of finding the longest heapable subsequence (as opposed to checking if the entire sequence is heapable) is still an open problem. Additionally, the behavior of sequences with limited "alphabet sizes" (few distinct values) and more complex hiring models with time-based constraints offer fertile ground for future research.
Summary updated