Skew heap

Skew heap

A skew heap is a variant of a binary heap. In contrast to e.g. leftist heaps, there is no structural constraint on skew heaps.

There are only two constraints left:
* The general heap order must be enforced
* Every operation (add, remove_min, merge) of two skew heaps must be done using a special "skew heap merge".

Definition

The following definition is Recursive definition.

*A heap with only one element is a skew heap.
*Given two skew heaps sh_1 and sh_2. The result of "skew merging" them is again a skew heap.

Skew Merge Operation

Consider two skew heaps. We want to merge them together.

We can do the same process as the merge of two Leftist heaps:

* Compare roots of two heaps
* Recursively merge the heap that has the larger root with the right subheap of the other one.
* Make the result heap as the right subheap of the heap that has smaller root.
* Swap the children of the new heap

Alternative, below is a clearer way (without recursive call, but you will have to do the sorting in the process):

*For this we take the rightest path (i.e. the path you go along when you always go right) from the rootnode. We "chop down" all the nodes we encounter: for each node on the rightest path, remove its right child. Do this for both skew heaps.

*Now we have some root nodes, which only have children on their left (if they have children at all). Now take all those root nodes you just created and sort them ascending.

*Finally, we connect these subtrees back together. Start at the far right (the highest root node key). The parent of this root node should be the second-to-last root node (as you sorted them earlier, they indeed have an order!). Continue to do this for all the rootnodes until you have one skew heap left.

*Now comes the trick of skewing. Every time you do connect a root node to its new parent p, flip both children of p.

This might sound strange in the beginning, because without any structural constraints, how can this structure be efficient at all?
Amortised complexity analysis shows out that all operations (thus the merge operation) can be done within O(log n).

Example

An example to demonstrate the merge operation on skew heaps:

*Chop down the nodes on the rightest path.

*Sort them ascendingly.

*Put 5 and 6 together.

*Put 4 and previous result together.

*Put 3 and previous result together.

*Put 2 and previous result together.

*Put 1 and previous result together. Finished.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Heap (data structure) — This article is about the programming data structure. For the dynamic memory area, see Dynamic memory allocation. Example of a complete binary max heap In computer science, a heap is a specialized tree based data structure that satisfies the heap …   Wikipedia

  • Leftist tree — A leftist tree or leftist heap is a priority queue implemented with a variant of a binary heap. Every node has an s value which is the distance to the nearest leaf. In contrast to a binary heap , a leftist tree attempts to be very unbalanced. In… …   Wikipedia

  • List of algebraic structures — In universal algebra, a branch of pure mathematics, an algebraic structure is a variety or quasivariety. Abstract algebra is primarily the study of algebraic structures and their properties. Some axiomatic formal systems that are neither… …   Wikipedia

  • Outline of algebraic structures — In universal algebra, a branch of pure mathematics, an algebraic structure is a variety or quasivariety. Abstract algebra is primarily the study of algebraic structures and their properties. Some axiomatic formal systems that are neither… …   Wikipedia

  • List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… …   Wikipedia

  • Список терминов, относящихся к алгоритмам и структурам данных —   Это служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавливается на информационные списки и глоссарии …   Википедия

  • Список терминов — Список терминов, относящихся к алгоритмам и структурам данных   Это сл …   Википедия

  • (s)ker-3 —     (s)ker 3     English meaning: to turn, bend     Deutsche Übersetzung: “drehen, biegen”     Note: (see also 1. (s)ker “ shrivel, shrink due to excess dryness, wrinkle up “ and 2. (s)ker ‘spring”)     Material: A. Av. skarǝna “ round “,… …   Proto-Indo-European etymological dictionary

  • Linked list — In computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum and a reference (in other words, a link) to the next node in the… …   Wikipedia

  • k̂lei- —     k̂lei     English meaning: to tip, incline, lean     Deutsche Übersetzung: “neigen, lehnen”; vielfach von angelehnten Stangen (hence Zelte with Stangengerippe; Sattelstangen), Leitern, leiter or gitterartigen Holzkonstruktionen, andrerseits… …   Proto-Indo-European etymological dictionary

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”