Soft Heaps Visualized
- ASU Author/Contributor (non-ASU co-authors, if there are any, appear on document)
- Shane McCann (Creator)
- Institution
- Appalachian State University (ASU )
- Web Site: https://library.appstate.edu/
- Advisor
- R. Mohan
Abstract: The soft heap is an approximate priority queue data structure originally proposed by Bernard Chazelle [3]. Chazelle used it to develop the fastest deterministic algorithm to compute a minimum spanning tree of a connected graph [2]. The soft heap allows some items to become “corrupted”, in which their keys are artificially increased. This allows us to overcome the sorting lower bound in the comparison-based model of computation. However, some of the corrupted items exit the heap out of order. The number of corrupted items in the heap is upper-bounded by em, where e is an error rate determined by the user, and m is the number of insertions into the heap. This corruption allows soft heap operations to run in constant amortized time for a suitable e = O(1), making it ideal for applications where speed is prioritized over precision. Such applications include finding an approximate median of a set of items, and in dynamic maintenance of percentiles [3]. Chazelle’s initial implementation of the soft heap uses a collection of binomial heaps. This was simplified in both implementation and analysis, by Kaplan and Zwick [10], and later by Kaplan, Zwick, and Tarjan [9], both of which use binary heap-ordered trees instead. In this thesis, we develop a visualization tool to visualize the soft heap implementation of Kaplan, Zwick, and Tarjan. We also visualize three applications in which soft heaps are used. Our web-based tool can be easily extended to make visualizations of other complex data structures and algorithms. For completeness, we provide a new presentation of the implementation and the analysis of Kaplan, Zwick, and Tarjan’s soft heap data structure. We hope that our presentation, along with the visualization tool, makes complex data structures and algorithms more accessible to early (and intermediate) computer science students. Whereas existing implementations may corrupt items during both insertions and deletions, we provide a slight modification of the delete-min operation, to include only single fillings, and thereby not corrupt any more items during deletions in the soft heap. Thus, our modification allows the soft heap data structure to be used as a black box, where corruption only comes from the insert operation, and ensures that only at most em total items (either in the heap or removed) are corrupted.
Soft Heaps Visualized
PDF (Portable Document Format)
979 KB
Created on 1/31/2024
Views: 26
Additional Information
- Publication
- Thesis
- McCann, S. (2023). Soft Heaps Visualized. Unpublished Master’s Thesis. Appalachian State University, Boone, NC.
- Language: English
- Date: 2023
- Keywords
- data structures, algorithms,
soft heap, visualization