A form of this structure allows combination of two blocks of size "2 to the n" into one block of size "2 to the n + 1" in constant time and supports key changes, while another variant of this structure with n elements has maximum node degree given by the log to the base of the golden ratio of n. This data structure is realized using a balanced search tree with time "big-O of log n" for insert and "big-O of 1" for delete-min and find-min operations, and is used to implement priority queues.
One form of this structure is balanced according to rank and supports a logarithmic time merge operation. Sleator and Tarjan invented a variant of that "leftist" form called the "skew" variant, which lacks balancing information and always performs an exchange operation. A form of this structure allows combination of two blocks of size "2 to the n" into one block of size "2 to the n + 1" in constant time and supports key changes, while another variant of this structure with n elements has maximum node degree given by the log to the base of the golden ratio of n. This data structure is realized using a balanced search tree with time "big-O of log n" for insert and "big-O of 1" for delete-min and find-min operations, and is used to implement priority queues. For 10 points, identify this tree-based data structure with the property that the key of a child is always less than the key of the parent.
One form of this structure is balanced according to rank and supports a logarithmic time merge operation.
heap