Editing Soft heap

{{Short description|Variant on the simple heap data structure}}
{{for|the band|Soft Heap}}
In [[computer science]], a '''soft heap''' is a variant on the simple [[heap (data structure)|heap data structure]] that has constant [[amortized analysis|amortized]] time complexity for 5 types of operations. This is achieved by carefully "corrupting" (increasing) the keys of at most a constant number of values in the heap.

==Definition and performance==
The constant time operations are:{{r|c|kz}}
* '''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 heap

Other heaps such as [[Fibonacci heap]]s achieve most of these bounds without any corruption, but cannot provide a constant-time bound on the critical ''delete'' operation. The amount of corruption can be controlled by the choice of a parameter <math>\varepsilon</math>, but the lower this is set, the more time insertions require: expressed using [[Big-O notation]], the [[amortized time]] will be <math>O(\log 1/\varepsilon)</math> for an error rate of <math>\varepsilon</math>.{{r|c|kz}} Some versions of soft heaps allow the ''create'', ''insert'', and ''meld'' operations to take constant time in the worst case, producing amortized rather than worst-case performance only for findmin and delete.{{r|ktz}} As with [[comparison sort]], these algorithms access the keys only by comparisons; if arithmetic operations on integer keys are allowed, the time dependence on <math>\varepsilon</math> can be reduced to <math>O(\log\log 1/\varepsilon)</math> or (with randomization) <math display=inline>O(\sqrt{\log\log 1/\varepsilon})</math>.{{r|tzz}}

More precisely, the error guarantee offered by the soft heap is the following: each soft heap is initialized with a parameter <math>\varepsilon</math>, chosen between 0 and 1/2. Then at any point in time it will contain at most <math>\varepsilon\cdot n</math> corrupted keys, where <math>n</math> is the number of elements inserted so far. Note that this does not guarantee that only a fixed percentage of the keys ''currently'' in the heap are corrupted: in an unlucky sequence of insertions and deletions, it can happen that all elements in the heap will have corrupted keys. Similarly, there is no guarantee that in a sequence of elements extracted from the heap with ''findmin'' and ''delete'', only a fixed percentage will have corrupted keys: in an unlucky scenario only corrupted elements are extracted from the heap. When a key is corrupted, the value stored for it in the soft key is higher than its initially-given value; corruption can never decrease the value of any key. The ''findmin'' operation finds the minimum value among the currently stored keys, including the corrupted ones.{{r|c|kz}}

The soft heap was designed by [[Bernard Chazelle]] in 2000. The term "corruption" in the structure 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. This is what makes soft heaps "soft"; one cannot be sure whether any particular value 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 theory|information-theoretic]] barriers regarding heaps.{{r|c}}

== Applications ==
Despite their limitations and unpredictable nature, soft heaps are useful in the design of deterministic algorithms. For instance, they have been used to achieve the best complexity to date for finding a [[minimum spanning tree]].{{r|mst}} Other problems whose efficient solution has been simplified using soft heaps include finding the <math>k</math>th smallest element in several classes of structured sets of values, including heap-ordered trees, sorted matrices, and [[sumset]]s.{{r|k2z2}}

Another simple example is a [[selection algorithm]], to find the <math>k</math>th smallest of a group of <math>n</math> numbers:{{r|c}}
*Initialize a soft heap with error rate <math>1/3</math>, allowing at most 33% of its inserted keys to be corrupted.
*Insert all <math>n</math> elements into the heap.
*Repeat <math>n/3</math> times: perform a findmin operation and delete the key that it returns.
*Let <math>L</math> be the deleted element whose correct key is largest.
*Compare <math>L</math> to all of the given elements, partition them into the subset less than <math>L</math> and the subset greater than <math>L</math>, placing elements that are equal to <math>L</math> into the first subset when they were deleted and into the second subset otherwise.
*Recursively call the same selection algorithm in the subset that contains the <math>k</math>th smallest.

After the comparison step of the algorithm, the first of the two subsets contains all of the deleted keys, so it includes at least <math>n/3</math> elements.
Among the <math>2n/3</math> elements that were not deleted, at most <math>n/3</math> are corrupted, so at least <math>n/3</math> are uncorrupted. These uncorrupted and undeleted elements must all belong to the second subset, because they are greater than or equal to the soft heap's (possibly corrupted) value of <math>L</math>, which is in turn greater than the true value of <math>L</math>. Thus, both subsets have between 33% and 66% of the elements. Because each level of recursion reduces the problem size by a constant factor, the total time of the algorithm can be bounded by a [[geometric series]], showing that it is <math>O(n)</math>.{{r|c}}

==References==
{{reflist|refs=

<ref name=c>{{cite journal |last=Chazelle |first=Bernard|author-link=Bernard Chazelle |title=The soft heap: an approximate priority queue with optimal error rate |journal=[[Journal of the ACM]] |volume=47 |issue=6 |date=November 2000 |pages=1012–1027 |doi=10.1145/355541.355554  |citeseerx=10.1.1.5.9705 |s2cid=12556140 |url=http://www.cs.princeton.edu/~chazelle/pubs/sheap.pdf}}</ref>

<ref name=mst>{{cite journal
 | last = Chazelle | first = Bernard | author-link = Bernard Chazelle
 | doi = 10.1145/355541.355562
 | issue = 6
 | journal = [[Journal of the ACM]]
 | mr = 1866456
 | pages = 1028–1047
 | title = A minimum spanning tree algorithm with inverse-Ackermann type complexity
 | volume = 47
 | year = 2000| doi-access = free
 }}</ref>

<ref name=kz>{{cite book |last1=Kaplan |first1=Haim |last2=Zwick |first2=Uri|author2-link=Uri Zwick |year=2009 |chapter-url=http://epubs.siam.org/doi/pdf/10.1137/1.9781611973068.53 |chapter=A simpler implementation and analysis of Chazelle's soft heaps |title=Proceedings of the Nineteenth Annual ACM–SIAM Symposium on Discrete Algorithms |publisher=Society for Industrial and Applied Mathematics |pages=477–485 |isbn=978-0-89871-680-1 |doi=10.1137/1.9781611973068.53 |citeseerx=10.1.1.215.6250}}</ref>

<ref name=k2z2>{{cite book
 | last1 = Kaplan | first1 = Haim
 | last2 = Kozma | first2 = László
 | last3 = Zamir | first3 = Or
 | last4 = Zwick | first4 = Uri | author4-link = Uri Zwick
 | editor1-last = Fineman | editor1-first = Jeremy T.
 | editor2-last = Mitzenmacher | editor2-first = Michael | editor2-link = Michael Mitzenmacher
 | contribution = Selection from heaps, row-sorted matrices, and X+Y using soft heaps
 | doi = 10.4230/OASICS.SOSA.2019.5
 | pages = 5:1–5:21
 | publisher = Schloss Dagstuhl – Leibniz-Zentrum für Informatik
 | series = OASIcs
 | title = 2nd Symposium on Simplicity in Algorithms, SOSA 2019, January 8–9, 2019, San Diego, CA, USA
 | volume = 69
 | year = 2019| doi-access = free
 }}</ref>

<ref name=ktz>{{cite journal
 | last1 = Kaplan | first1 = Haim
 | last2 = Tarjan | first2 = Robert E. | author2-link = Robert Tarjan
 | last3 = Zwick | first3 = Uri | author3-link = Uri Zwick
 | doi = 10.1137/120880185
 | issue = 4
 | journal = [[SIAM Journal on Computing]]
 | mr = 3084181
 | pages = 1660–1673
 | title = Soft heaps simplified
 | volume = 42
 | year = 2013}}</ref>

<ref name=tzz>{{cite conference
 | last1 = Thorup | first1 = Mikkel | author1-link = Mikkel Thorup
 | last2 = Zamir | first2 = Or
 | last3 = Zwick | first3 = Uri | author3-link = Uri Zwick
 | editor1-last = Baier | editor1-first = Christel
 | editor2-last = Chatzigiannakis | editor2-first = Ioannis
 | editor3-last = Flocchini | editor3-first = Paola
 | editor4-last = Leonardi | editor4-first = Stefano
 | contribution = Dynamic ordered sets with approximate queries, approximate heaps and soft heaps
 | doi = 10.4230/LIPICS.ICALP.2019.95
 | pages = 95:1–95:13
 | publisher = Schloss Dagstuhl – Leibniz-Zentrum für Informatik
 | series = LIPIcs
 | title = 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9–12, 2019, Patras, Greece
 | volume = 132
 | year = 2019| doi-access = free }}</ref>

}}

[[Category:Heaps (data structures)]]
[[Category:Amortized data structures]]