Soft heap

Soft heap

In computer science, the soft heap, designed by Bernard Chazelle in 2000, is a variant on the simple heap data structure. By carefully "corrupting" (increasing) the keys of at most a certain fixed percentage of values in the heap, it is able to achieve amortized constant-time bounds for all five of its operations:
* create("S"): Create a new soft heap
* insert("S", "x"): Insert an element into a soft heap
* meld("S", " S' "): Combine the contents of two soft heaps into one, destroying both
* delete("S", "x"): Delete an element from a soft heap
* findmin("S"): Get the element with minimum key in the soft heapThe term "corruption" here is the result of what Chazelle called "carpooling" in a soft heap. Each node in the soft heap contains a linked-list of keys and one common key. The common key is an upper bound on the values of the keys in the linked-list. Once a key is added to the linked-list, it is considered corrupted because its value is never again relevant in any of the soft heap operations: only the common keys are compared. It is unpredictable which keys will be corrupted in this manner; it is only known that at most a fixed percentage will be corrupted. This is what makes soft heaps "soft"; you can't be sure whether or not any particular value you put into it will be corrupted. The purpose of these corruptions is effectively to lower the information entropy of the data, enabling the data structure to break through information-theoretic barriers regarding heaps.

Other heaps such as fibonacci heaps achieve most of these bounds without any corruption, but cannot provide a constant-time bound on the critical "delete" operation. The percentage of values which are corrupted can be chosen freely, but the lower this is set, the more time insertions require (O(log 1/ε) for an error rate of ε).

Applications

Surprisingly, soft heaps are useful in the design of deterministic algorithms, despite their unpredictable nature. They were the key in creating the best-known algorithm for finding a minimum spanning tree to date. They can also be used to easily build an optimal selection algorithm, as well as "near-sorting" algorithms, which are algorithms that place every element near its final position, a situation in which insertion sort is fast.

One of the simplest examples is the selection algorithm. Say we want to find the "k"th largest of a group of "n" numbers. First, we choose an error rate of 1/4; that is, at most 25% of the keys we insert will be corrupted. Now, we insert all "n" elements into the heap — at this point, at most "n"/4 keys are corrupted. Next, we delete the minimum element from the heap "n"/2 times. Because this is decreasing the size of the heap, it cannot increase the number of corrupted elements. The result is that, still, at most "n"/4 keys are corrupted.

Thus, at least "n"/2 − "n"/4 = "n"/4 of the remaining keys are not corrupted, and each must be larger than every element we removed. Moreover, because keys are only increased by corruption, the last and largest element "L" we removed must exceed the original keys of the "n"/4 other elements we removed. In other words, "L" divides the elements somewhere between 25%/75% and 75%/25%. We then partition the set about "L" using the "partition" algorithm from quicksort and apply the same algorithm again to either the set of numbers less than "L" or the set of numbers greater than "L", neither of which can exceed (3/4)"n" elements. Since each insertion and deletion requires O(1) amortized time, the total deterministic time is bounded by a multiple of:

T("n") = (5/4)"n" + (5/4)(3/4)"n" + (5/4)(3/4)2"n" + ... = 5n.

The final algorithm looks like this:

function softHeapSelect(a [1..n] , k) if k = 1 then return minimum(a [1..n] ) create(S) for i from 1 to n insert(S, a [i] ) for i from 1 to n/4 x := findmin(S) delete(S, x) xIndex := partition(a, x) "// Returns new index of pivot x" if k < xIndex softHeapSelect(a [1..xIndex-1] , k) else softHeapSelect(a [xIndex..n] , k-xIndex+1)

External links

* Chazelle's original paper [http://www.cs.princeton.edu/~chazelle/pubs/sheap.ps (ps)] [http://www.cs.princeton.edu/~chazelle/pubs/sheap.pdf (pdf)] directly from the author's website, including C code.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Soft Heap — was a Canterbury scene supergroup founded in January 1978. The name references Soft Machine while Heap comes from the first letters of the band s founders: Hugh Hopper (bass), Elton Dean (saxophone), Alan Gowen (keyboards) and Pip Pyle (drums).… …   Wikipedia

  • Soft Heap — fue un supergrupo de la Escena de Canterbury fundado en junio de 1978. Soft hace referencia a Soft Machine y Heap a las iniciales de los nombres de los cuatro músicos fundadores: Hugh Hopper (bajo), Elton Dean (saxofón), Alan Gowen (teclados) and …   Wikipedia Español

  • Soft Machine — Pays d’origine Canterbury, Angleterre  Royaume Uni Genre musical Rock progressif Rock psychédélique …   Wikipédia en Français

  • Soft machine — est un groupe de rock britannique, pionnier dans le psychédélisme. Son nom est inspiré du livre éponyme de William S. Burroughs. Formé en 1966 à Canterbury par Robert Wyatt (batterie et chant), Mike Ratledge (orgue, piano), Daevid Allen (guitare) …   Wikipédia en Français

  • Soft — Business* Adventure Soft, UK based video game developer which was established in the 1980s by Mike Woodroffe * Cocktail Soft, Japanese H game manufacturer * Hudson Soft, Japanese publisher and developer * Illusion Soft, company from Yokohama,… …   Wikipedia

  • Heap (data structure) — This article is about the programming data structure. For the dynamic memory area, see Dynamic memory allocation. Example of a complete binary max heap In computer science, a heap is a specialized tree based data structure that satisfies the heap …   Wikipedia

  • Soft Machine — Infobox musical artist Name = Soft Machine Img capt = Group photo circa 1970: Elton Dean, Mike Ratledge, Robert Wyatt, Hugh Hopper Img size = Landscape = Yes Background = group or band Alias = The Soft Machine Origin = Canterbury, England, United …   Wikipedia

  • Heap (Datenstruktur) — In der Informatik ist ein Heap (wörtlich Haufen oder Halde) eine zumeist auf Bäumen basierende abstrakte Datenstruktur. In einem Heap können Objekte oder Elemente abgelegt und aus diesem wieder entnommen werden. Sie dienen damit der Speicherung… …   Deutsch Wikipedia

  • Binomial heap — In computer science, a binomial heap is a heap similar to a binary heap but also supporting the operation of merging two heaps quickly. This is achieved by using a special tree structure. It is important as an implementation of the mergeable heap …   Wikipedia

  • Max-Heap — In der Informatik ist ein Heap (wörtlich Haufen oder Halde) eine zumeist auf Bäumen basierende abstrakte Datenstruktur. In einem Heap können Objekte oder Elemente abgelegt und aus diesem wieder entnommen werden. Sie dienen damit der Speicherung… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”