TY - JOUR

T1 - Meldable heaps and Boolean union-find

AU - Kaplan, Haim

AU - Shafrir, Nira

AU - Tarjan, Robert Endre

PY - 2002/9/23

Y1 - 2002/9/23

N2 - In the classical meldable heap data type we maintain an item-disjoint collection of heaps under the operations findmin, insert, delete, decrease-key, and meld. In the usual definition decrease-key and delete get the item and the heap containing it as parameters. We consider the modified problem where decrease-key and delete get only the item but not the heap containing it. We show that for this problem one of the operations find-min, decrease-key, or meld must take non-constant time. This is in contrast with the original data type in which data structures supporting all these three operations in constant time are known (both in an amortized and a worst-case setting). To establish our results for meldable heaps we consider a weaker version of the union-find problem that is of independent interest, which we call Boolean union-find. In the Boolean union-find problem the find operation is a binary predicate that gets an item x and a set A and answers positively if and only if x ∈ A. We prove that the lower bounds which hold for union-find in the cell probe model hold for Boolean union-find as well. We also suggest new heap data structures implementing the modified meldable heap data type that are based on redundant binary counters. Our data structures have good worst-case bounds. The best of our data structures matches the worst-case lower bounds which we establish for the problem. The simplest of our data structures is an interesting generalization of binomial queues.

AB - In the classical meldable heap data type we maintain an item-disjoint collection of heaps under the operations findmin, insert, delete, decrease-key, and meld. In the usual definition decrease-key and delete get the item and the heap containing it as parameters. We consider the modified problem where decrease-key and delete get only the item but not the heap containing it. We show that for this problem one of the operations find-min, decrease-key, or meld must take non-constant time. This is in contrast with the original data type in which data structures supporting all these three operations in constant time are known (both in an amortized and a worst-case setting). To establish our results for meldable heaps we consider a weaker version of the union-find problem that is of independent interest, which we call Boolean union-find. In the Boolean union-find problem the find operation is a binary predicate that gets an item x and a set A and answers positively if and only if x ∈ A. We prove that the lower bounds which hold for union-find in the cell probe model hold for Boolean union-find as well. We also suggest new heap data structures implementing the modified meldable heap data type that are based on redundant binary counters. Our data structures have good worst-case bounds. The best of our data structures matches the worst-case lower bounds which we establish for the problem. The simplest of our data structures is an interesting generalization of binomial queues.

UR - http://www.scopus.com/inward/record.url?scp=0036040064&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0036040064&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:0036040064

SP - 573

EP - 582

JO - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

JF - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

SN - 0734-9025

ER -