Template:Heap Running Times: Revision history

3 August 2024

• curprev 12:3812:38, 3 August 2024 Maëlan talk contribs 12,744 bytes +18 the given sources describe "structural abstraction" / "datastructural bootstrapping" only for persistent data structures; I think it can also be done for imperative data structures, but it is not entirely obvious, and it doesn’t tell how to implement ''decrease-min''; also, shorten some bits of this footnote undo
• curprev 12:1812:18, 3 August 2024 Maëlan talk contribs 12,726 bytes −28 even shorter undo
• curprev 12:1712:17, 3 August 2024 Maëlan talk contribs 12,754 bytes −329 shorten footnotes again as said in talk page undo

31 July 2024

• curprev 23:2823:28, 31 July 2024 IntGrah talk contribs 13,083 bytes +545 It already requires meld to be logarithmic, so explicitly excluding Binary heaps isn't strictly necessary, but I'll give you it since Floyd's method is briefly mentioned. I reworded the double "respectively" sentence; saying "respectively x and y" twice doesn't mean anything to me. I changed the wording to a version I think is clearer than my own first attempt undo Tag: 2017 wikitext editor
• curprev 21:4021:40, 31 July 2024 Maëlan talk contribs 12,538 bytes 0 swap columns for "decrease-key" and "insert" (because "decrease-key" is somewhat related to "delete-min", while "insert" is strongly related to "meld") undo
• curprev 21:2821:28, 31 July 2024 Maëlan talk contribs m 12,538 bytes +95 nbsp undo
• curprev 21:2421:24, 31 July 2024 Maëlan talk contribs 12,443 bytes −52 shorten footnotes perhaps undo
• curprev 21:2221:22, 31 July 2024 Maëlan talk contribs 12,495 bytes +1,227 improve notes about structural abstraction, Brodal-Okasaki, and optimality undo
• curprev 20:2720:27, 31 July 2024 Maëlan talk contribs 11,268 bytes +141 clearer wording; doesn’t apply to binary heaps undo
• curprev 17:4717:47, 31 July 2024 IntGrah talk contribs 11,127 bytes −395 Move make-heap footnotes to column header undo Tag: 2017 wikitext editor
• curprev 17:4017:40, 31 July 2024 IntGrah talk contribs m 11,522 bytes −406 Undid revision 1237825236 by Maëlan (talk) I'm not sure this is necessary to put in a note – I would regard tracking the minimum as part of the structure definition by default. undo Tag: Undo
• curprev 17:2617:26, 31 July 2024 Maëlan talk contribs 11,928 bytes +406 add note about find-min in binomial or Fibonacci heaps undo Tag: Reverted
• curprev 16:3016:30, 31 July 2024 Maëlan talk contribs 11,522 bytes 0 reorder "skew" before "leftist" (because skew has the same complexities as leftist but skew is amortized whereas leftist is worst-case, thus leftist is better) and "bottom-up skew" below "2-3 heaps" (because bottom-up skew is better for meld; also, this reduces possible confusion for anyone reading the table, by moving "bottom-up skew" further from the unrelated "skew binomial") ("bottom-up skew" was originally next to "skew" because it is a variant of it, which itself is a variant of "leftist") undo
• curprev 12:2012:20, 31 July 2024 IntGrah talk contribs 11,522 bytes 0 Reorder undo Tag: 2017 wikitext editor

25 July 2024

• curprev 05:4005:40, 25 July 2024 Maëlan talk contribs 11,522 bytes +358 →top: move the "amortized" indication out of footnotes, to make it more visible undo
• curprev 05:3005:30, 25 July 2024 Maëlan talk contribs 11,164 bytes +1,598 →top: add ref for leftist heaps; add make-heap (it is well-known, interesting, and eminently non-trivial, that it can be done in linear time; it is true for every heap implementation in this table, but for different reasons!) undo
• curprev 03:5803:58, 25 July 2024 Maëlan talk contribs 9,566 bytes +185 →top: the optimization of meld applies to other implementations too, yielding amortized complexity undo
• curprev 03:5103:51, 25 July 2024 Maëlan talk contribs 9,381 bytes +5 replace some big-O with big-Thetas, undoing changes 1 and 2 by Alex Kindel, see talk page undo
• curprev 03:3603:36, 25 July 2024 Maëlan talk contribs 9,376 bytes +1,131 add skew heap and bottom-up skew heap undo

1 June 2024

• curprev 16:2616:26, 1 June 2024 SoulSneezer talk contribs 8,245 bytes 0 Undid revision 1226752259 by SoulSneezer (talk) undo Tag: Undo
• curprev 16:1116:11, 1 June 2024 SoulSneezer talk contribs m 8,245 bytes 0 Fixed minor typo undo Tag: Reverted
• curprev 15:5915:59, 1 June 2024 SoulSneezer talk contribs 8,245 bytes +11 Changed time complexity of meld operation on 2-3 heap undo

29 May 2024

• curprev 12:0312:03, 29 May 2024 SoulSneezer talk contribs m 8,234 bytes −14 Changed time complexity of insert operation on 2-3 heaps to Θ(1) amortized(as mentioned in the original paper). Find-min can be implemented in Θ(1) using a pointer to the minimum. undo

23 April 2024

• curprev 22:0222:02, 23 April 2024 IntGrah talk contribs 8,248 bytes +7 Add link to strict Fibonacci undo

13 July 2023

• curprev 08:3208:32, 13 July 2023 Maëlan talk contribs 8,241 bytes −110 remove obvious (?) footnote undo
• curprev 08:3108:31, 13 July 2023 Maëlan talk contribs 8,351 bytes +986 + skew binomial undo

10 July 2023

• curprev 12:5012:50, 10 July 2023 Maëlan talk contribs 7,365 bytes 0 sort implementations by overall asymptotic performance undo

16 December 2020

• curprev 20:2120:21, 16 December 2020 Monkbot talk contribs m 7,365 bytes +11 Task 18a (cosmetic) (manual): eval 10 templates: hyphenate params (11×); undo Tag: AWB

29 October 2020

• curprev 18:0318:03, 29 October 2020 92.119.17.10 talk 7,354 bytes +2 Use dash rather than hyphen in 2–3 heap undo

11 October 2020

• curprev 20:0520:05, 11 October 2020 Headbomb talk contribs m 7,352 bytes −10 →top: no longer needed, removed: |ref=harv undo Tag: AWB

29 September 2020

• curprev 16:0916:09, 29 September 2020 Pcgomes talk contribs 7,362 bytes +220 Make template flexible for either max or min heap undo

4 October 2019

• curprev 06:1806:18, 4 October 2019 DestinationIrrational talk contribs 7,142 bytes +224 Including the find-min time complexity for 2-3 heap. undo

1 October 2019

• curprev 19:1819:18, 1 October 2019 100.36.186.72 talk 6,918 bytes 0 Fix color inconsistency for Binomial Heap: Find-min undo

30 September 2019

• curprev 08:3908:39, 30 September 2019 EtaoinWu talk contribs 6,918 bytes +177 Change the time complexity of "find-min" of Binomial heap data structure. undo Tag: 2017 wikitext editor

2 July 2019

• curprev 05:3005:30, 2 July 2019 167.88.12.231 talk 6,741 bytes −2 Per Heap and standard usage in the literature, call the destructive combining operation "meld" rather than "merge" undo

1 May 2019

• curprev 21:0521:05, 1 May 2019 Alexey Muranov talk contribs 6,743 bytes −15 Rewrite the introduction paragraph. (In particular, trying to define or summarize here the meaning of "big O" is useless: ether the reader already knows it, or it is not going to help.) undo

4 April 2019

• curprev 02:2902:29, 4 April 2019 Negiizhao talk contribs 6,758 bytes +3 No edit summary undo

10 March 2019

• curprev 09:3009:30, 10 March 2019 Jonesey95 talk contribs 6,755 bytes +1 Fix Linter errors undo
• curprev 03:3803:38, 10 March 2019 209.209.238.189 talk 6,754 bytes +301 Improve existing refs with citeseerx links, authorlinks, etc. undo

3 March 2019

• curprev 04:3804:38, 3 March 2019 209.209.238.189 talk 6,453 bytes −4 Transpose table to avoid excessive width. Now 6 columns, 10 rows, and additional heap types add rows rather than width. undo
• curprev 04:2404:24, 3 March 2019 209.209.238.189 talk 6,457 bytes +50 Stop stupid line breaks between "log" and "n". Better having to horizontally scroll than read that mess. undo

16 December 2018

• curprev 22:2822:28, 16 December 2018 Alex Kindel talk contribs 6,407 bytes −1 Decrease-key operation may terminate in constant time binary binary heaps and therefor is not lower-bound logn but O(1), making it O(log n) and not Theta(log n) undo

12 December 2018

• curprev 02:4702:47, 12 December 2018 Senator2029 talk contribs 6,408 bytes +5 Reverted good faith edits by Negiizhao (talk): Unexplained changes that could affect validity of the information . (TW) undo Tag: Undo
• curprev 01:5601:56, 12 December 2018 Negiizhao talk contribs 6,403 bytes −5 No edit summary undo

27 November 2018

• curprev 21:0221:02, 27 November 2018 129.7.106.20 talk 6,408 bytes −4 fixed formatting of "pages" in citations undo
• curprev 20:5820:58, 27 November 2018 129.7.106.20 talk 6,412 bytes −6 No edit summary undo

16 August 2018

• curprev 17:5717:57, 16 August 2018 2001:4898:80e8:9:84be:5f51:bffb:8ebe talk 6,418 bytes +260 add a column with running time info for the 2-3 heap based on paper 'Theory of the 2-3 heap' undo

8 January 2018

• curprev 17:2717:27, 8 January 2018 David Eppstein talk contribs 6,158 bytes +8 edition= ? undo

2 October 2017

• curprev 09:1409:14, 2 October 2017 140.112.238.211 talk 6,150 bytes −4 No edit summary undo
• curprev 09:0209:02, 2 October 2017 140.112.238.171 talk 6,154 bytes +254 No edit summary undo