Page 224 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Anil Sharma, Lovely Professional University
Unit 11: Leftist Heaps and Binomial Queues

Unit 11: Leftist Heaps and Binomial Queues Notes

CONTENTS

Objectives
Introduction
11.1 Leftist Heaps
11.1.1 Leftist Trees
11.1.2 Implementation
11.1.3 Merging Leftist Heaps
11.1.4 Putting items into a Leftist Heap
11.1.5 Removing items from a Leftist Heap
11.2 Skew Heaps
11.3 Binomial Queues
11.4 Summary

11.5 Keywords
11.6 Self Assessment
11.7 Review Questions
11.8 Further Readings

Objectives

After studying this unit, you will be able to:
State the concept leftist heaps

Realise skew heaps
Explain the binomial queues

Introduction

Numerous data structures have been developed that can support efficient implementations of

all the priority-queue operations. Most of them are based on direct linked representation of
heap-ordered trees. Two links are needed for moving down the tree (either to both children in a
binary tree or to the first child and next sibling in a binary tree representation of a general tree)

and one link to the parent is needed for moving up the tree. Developing implementations of
the heap-ordering operations that work for any (heap-ordered) tree shape with explicit nodes

and links or other representation is generally straightforward. The difficulty lies in dynamic
operations such as insert, remove, and join, which require us to modify the tree structure.
Different data structures are based on different strategies for modifying the tree structure while
still maintaining balance in the tree.

11.1 Leftist Heaps

A leftist heap is a heap-ordered binary tree which has a very special shape called a leftist tree.
One of the nice properties of leftist heaps is that is possible to merge two leftist heaps effi ciently.
As a result, leftist heaps are suited for the implementation of mergeable priority queues.

LOVELY PROFESSIONAL UNIVERSITY 219