Brodal queue

{{Infobox data structure

| name = Brodal queue

| image =

| alt =

| caption =

| type = Heap/priority queue

| invented_by = Gerth Stølting Brodal

| invented_year = 1996

| space_avg =

| space_worst =

| search_avg =

| search_worst =

| insert_avg =

| insert_worst =

| delete_avg =

| delete_worst =

| peek_avg =

| peek_worst =

| find_min_avg =

| find_min_worst =

| delete_min_avg =

| delete_min_worst =

| decrease_key_avg =

| decrease_key_worst =

| merge_avg =

| merge_worst =

}}{{Short description|Optimal data structure for priority queue operations}}

In computer science, the Brodal queue is a heap/priority queue structure with very low worst case time bounds: $O(1)$ for insertion, find-minimum, meld (merge two queues) and decrease-key and $O(\backslash mathrm\{log\}(n))$ for delete-minimum and general deletion. They are the first heap variant to achieve these bounds without resorting to amortization of operational costs. Brodal queues are named after their inventor Gerth Stølting Brodal.Gerth Stølting Brodal (1996). Worst-case efficient priority queues. Proc. 7th ACM-SIAM Symposium on Discrete Algorithms, pp. 52–58

While having better asymptotic bounds than other priority queue structures, they are, in the words of Brodal himself, "quite complicated" and "[not] applicable in practice." Brodal and Okasaki describe a persistent (purely functional) version of Brodal queues.Gerth Stølting Brodal and Chris Okasaki (1996). [http://www.brics.dk/RS/96/37/BRICS-RS-96-37.pdf Optimal purely functional priority queues]. Journal of Functional Programming.