Sleator and Tarjan invented a variant of that "leftist" form called the "skew" variant, which lacks balancing information and always performs an exchange operation.
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