Binomial, Fibonacci, and Pairing Heaps:Related Developments.

By -

Related Developments

In this section we describe some results pertinent to the data structures of this chapter. First, we discuss a variation of the pairing heap, referred to as the skew-pairing heap. The skew-pairing heap appears as a form of “missing link” in the landscape occupied by pairing heaps and skew heaps (Chapter 6). Second, we discuss some adaptive properties of pairing heaps. Finally, we take note of soft heaps, a new shoot of activity emanating from the primordial binomial heap structure that has given rise to the topics of this chapter.

Skew-Pairing Heaps

There is a curious variation of the pairing heap which we refer to as a skew-pairing heap – the name will become clear. Aside from the linking process used for combining subtrees in the extractmin operation, skew-pairing heaps are identical to two-pass pairing heaps.

The skew-pairing heap extractmin linking process places greater emphasis on right-to-left linking than does the pairing heap, and proceeds as follows.

First, a right-to-left linking of the subtrees that fall in odd numbered positions is executed. Let Hodd denote the result. Similarly, the subtrees in even numbered positions are linked in right-to-left order. Let Heven denote the result. Finally, we link the two trees, Hodd and Heven . Figure 7.14 illustrates the process.

The skew-pairing heap enjoys O(log n) time bounds for the usual operations. Moreover, it has the following curious relationship to the skew heap. Suppose a finite sequence S of

image

meld and extractmin operations is executed (beginning with heaps of size 1) using (a) a skew heap and (b) a skew-pairing heap. Let Cs and Cs−p be the respective sets of comparisons between keys that actually get performed in the course of the respective executions (ignoring the order of the comparison executions). Then Cs−p ⊂ Cs [4]. Moreover, if the sequence S terminates with the heap empty, then Cs−p = Cs. (This inspires the name “skew-pairing”.) The relationship between skew-pairing heaps and splay trees is also interesting. The child, sibling transformation, which for two-pass pairing heaps transforms the extractmin operation into a splay operation on a search tree path having no bends, when applied to the skew-pairing heap, transforms extractmin into a splay operation on a search tree path having a bend at each node. Thus, skew-pairing heaps and two-pass pairing heaps demarcate opposite ends of a spectrum.

Adaptive Properties of Pairing Heaps

Consider the problem of merging k sorted lists of respective lengths n1, n2, ··· , nk, with ni = n. The standard merging strategy that performs lg k rounds of pairwise list merges requires n lg k time. However, a merge pattern based upon the binary Huffman tree, having minimal external path length for the weights n1, n2, ··· , nk , is more efficient when the lengths ni are non-uniform, and provides a near optimal solution. Pairing heaps can be utilized to provide a rather different solution as follows. Treat each sorted list as a linearly structured pairing heap. Then (a) meld these k heaps together, and (b) repeatedly execute extractmin operations to retrieve the n items in their sorted order. The number of comparisons that take place is bounded by

image

Since the above multinomial coefficient represents the number of possible merge patterns, the information-theoretic bound implies that this result is optimal to within a constant factor. The pairing heap thus self-organizes the sorted list arrangement to approximate an optimal merge pattern. Iacono has derived a “working-set” theorem that quantifies a similar adaptive property satisfied by pairing heaps. Given a sequence of insertion and extractmin operations initiated with an empty heap, at the time a given item x is deleted we can attribute to x a contribution bounded by O(log op(x)) to the total running time of the sequence, where op(x) is the number of heap operations that have taken place since x was inserted (see [8] for a slightly tighter estimate). Iacono has also shown that this same bound applies for skew and skew-pairing heaps [8]. Knuth [10] has observed, at least in qualitative terms, similar behavior for leftist heaps . Quoting Knuth:

Leftist trees are in fact already obsolete, except for applications with a strong tendency towards last-in-first-out behavior.

Soft Heaps

An interesting development (Chazelle [1]) that builds upon and extends binomial heaps in a different direction is a data structure referred to as a soft heap. The soft heap departs from the standard notion of priority queue by allowing for a type of error, referred to as corruption, which confers enhanced efficiency. When an item becomes corrupted, its key value gets increased. Findmin returns the minimum current key, which might or might not be corrupted. The user has no control over which items become corrupted, this prerogative belonging to the data structure. But the user does control the overall amount of corruption in the following sense.

The user specifies a parameter, 0 < E ≤ 1/2, referred to as the error rate, that governs the behavior of the data structure as follows. The operations findmin and deletion are supported in constant amortized time, and insertion is supported in O(log 1/E) amortized

time. Moreover, no more than an E fraction of the items present in the heap are corrupted at any given time.

To illustrate the concept, let x be an item returned by findmin, from a soft heap of size n. Then there are no more than En items in the heap whose original keys are less than the original key of x.

Soft heaps are rather subtle, and we won’t attempt to discuss specifics of their design. Soft heaps have been used to construct an optimal comparison-based minimum spanning tree algorithm (Pettie and Ramachandran [12]), although its actual running time has not been determined. Soft heaps have also been used to construct a comparison-based algorithm with known running time mα(m, n) on a graph with n vertices and m edges (Chazelle [2]), where α(m, n) is a functional inverse of the Ackermann function. Chazelle [1] has also observed that soft heaps can be used to implement median selection in linear time; a significant departure from previous methods.

Comments

Post a Comment

Popular posts from this blog

0/1 Knapsack Problem Memory function.

By -
Image
0 / 1 Knapsack Problem Memory function Definition: Given a set of n items of known weights w1,…,wn and values v1,…,vn and a knapsack of capacity W, the problem is to find the most valuable subset of the items that fit into the knapsack. Knapsack problem is an OPTIMIZATION PROBLEM Dynamic programming approach to solve knapsack problem Step 1: Identify the smaller sub-problems. If items are labeled 1..n, then a sub-problem would be to find an optimal solution for Sk = {items labeled 1, 2, .. k } Step 2: Recursively define the value of an optimal solution in terms of solutions to smaller problems. Initial conditions: S te p 3: Bottom up computation using iteration Question: Apply bottom-up dynamic programming algorithm to the following instance of the knapsack problem Capacity W= 5 Solution: Using dynamic programming approach, we have: What is the composition of the optimal subset? The composition of the optimal subset if found by tracing back the computations for the...
Read more

Binary Space Partitioning Trees:BSP Tree as a Hierarchy of Regions.

By -
Image
BSP Tree as a Hierarchy of Regions Another way to look at BSP Trees is to focus on the hierarchy of regions created by the recursive partitioning, instead of focusing on the hyperplanes themselves. This view helps us to see more easily how intersections are efficiently computed. The key idea is to think of a BSP Tree region as serving as a bounding volume: each node v corresponds to a convex volume that completely contains all the geometry represented by the sub tree rooted at v . Therefore, if some other geometric entity, such as a point, ray, object, etc., is found to not intersect the bounding volume, then no intersection computations need be performed with any geometry within that volume. Consider as an example a situation in which we are given some test point and we want to find which object if any this point lies in. Initially, we know only that the point lies somewhere space ( Figure 20.12). By comparing the location of the point with respect to the first partitioning hyper pl...
Read more

Drawing Trees:HV-Layout

By -
Image
HV-Layout An hv -layout of a binary tree is an upward (but not strictly upward) straight line orthogonal drawing with edges drawn as rightward horizontal or downward vertical segments. The ”hv” stands for horizontal-vertical. For any vertex v in a binary tree T we either have: 1. A child of v is either • aligned horizontally with v and to the right of v or • vertically aligned below v . 2. The smallest rectangles that cover the area of the subtrees of the children of v in the layout do not intersect. Figure 45.12 shows an example of a hv -layout A hv -layout is generated by applying a dived and conquer approach. The divide step constructs the hv -layout of the left and the right subtrees, while the conquer step either performs a ho rizontal or a ver t i c a l combination . Figure 45.13 shows the two types of com- bination. If the left subtree a node v is placed to the left in a horizontal combination and below in a vertical combination, the layout preserves ...
Read more