AF: Small: Understanding Fudnamental Data Structures

高效存储和访问数据的需求是现代计算的核心，而存储和访问数据的方法的设计和分析构成了数据结构领域。这个项目将研究发现几个基本问题的可证明的最佳数据结构，包括字典和优先级队列。字典支持有序数据的高效插入、删除和搜索。优先级队列支持插入和删除最小元素。数据结构将在基于实例的最优性范式下进行设计和分析。在这个模型中，一个数据结构在操作序列上的性能是根据它与自然定义的结构类中该序列的最佳结构的速度相比有多好来评估的。将要研究的结构类型包括二叉搜索树和堆。二叉搜索树和堆可以说是计算机科学中最基本的非平凡数据结构类。尽管它们起源于计算机时代，但直到今天，对这类结构的全面理解仍然是难以捉摸的。对基本数据结构的其他操作将进行研究。减少堆中某项值的能力对某些算法至关重要，特别是Dijkstra在图中寻找单源最短路径的算法。然而，人们还不完全了解什么类型的结构可以有效地支持这种操作。此外，目前还没有已知的有效方法来支持字典的拆分和合并；这个项目的一个目标是设计一个基于比较的字典，在平摊对数时间内完成这个任务。

The need to efficiently store and access data is central to modern computing, and the design and analysis of methods to store and access data constitutes the field of data structures. This project will investigate the discovery of provably best data structures for several fundamental problems, including the dictionary and the priority queue. The dictionary supports the efficient insertion, deletion, and search of ordered data. The priority queue supports insertion and the removal of the minimum element.Data structures will be designed and analyzed under the paradigm of instance-based optimality. In this model, a data structure's performance on a sequence of operations is evaluated based on how well it compares to the speed of the best structure for that sequence among a naturally-defined class of structures. The classes of structures that will be examined include binary search trees and heaps. Binary search trees and heaps are arguably the most fundamental nontrivial classes of data structures in computer science. Despite their origins at the dawn of computing, a complete understanding of these classes of structures has remained elusive to this day.Other operations on fundamental data structures will be investigated. The ability to decrease the value of an item in a heap is vital to some algorithms, notably Dijkstra's algorithm for finding single-source shortest paths in a graph. Yet, it is not completely understood what types of structures can support this operation efficiently. Also, there is no known efficient method to support the splitting and merging of dictionaries; one goal of this project is to design a comparison-based dictionary do this in amortized logarithmic time.