Book Image

Everyday data structures

By : William Smith
Book Image

Everyday data structures

By: William Smith

Overview of this book

Explore a new world of data structures and their applications easily with this data structures book. Written by software expert William Smith, you?ll learn how to master basic and advanced data structure concepts. ? Fully understand data structures using Java, C and other common languages ? Work through practical examples and learn real-world applications ? Get to grips with data structure problem solving using case studies
Table of Contents (20 chapters)
Everyday Data Structures
Credits
About the Author
About the Reviewer
www.PacktPub.com
Customer Feedback
Preface
Free Chapter
1
Data Types: Foundational Structures

Heap operations


Not all implementations of the heap data structures expose the same operational methods. However, the more common operations should be available or made available as needed by the developer.

  • Insert: The Insert operation adds a new node to the heap. This operation must also re-order the heap to ensure that the newly added node maintains the heap property. This operation has an O(log n) operational cost.

  • FindMax: The FindMax operation is synonymous with a max heap, and returns the largest value or highest-priority object in the collection. In an array-based implementation, this is typically the object at either index 0 or index 1, depending on the design. This is equivalent to the peek operation in a stack or queue, which is important when using a heap to implement a priority queue. This operation has an O(1) operational cost.

  • FindMin: The FindMin operation is related to a min heap, and returns the smallest value or lowest-priority object in the collection. In an array-based implementation...