Pattern Avoidance in k-ary Heaps

Abstract

In this paper, we consider pattern avoidance in k-ary heaps, where the permutation associated with the heap is found by recording the nodes as they are encountered in a breadth-first search. We enumerate heaps that avoid patterns of length 3 and collections of patterns of length 3, first with binary heaps and then more generally with k-ary heaps. 1