Understanding Heap Data Structure Implementation

Explore the implementation of a heap data structure through a complete binary tree concept, array representation, adding elements, removing elements, and avoiding swaps. Learn the steps involved in adding, removing, and organizing elements within a heap for efficient data storage and retrieval.

• Heap Data Structure
• Binary Tree
• Array Representation
• Element Addition
• Swaps

kend_560 Follow

Uploaded on Sep 10, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. A Heap Implementation Chapter 26 1 Adapted from Pearson Education, Inc.

2. Heaps (ch23) Complete binary tree: nodes contain Comparable objects Organization Each node contains object no smaller (or no larger) than objects in descendants Maxheap, object in node greater than or equal to descendant objects Minheap, object in node less than or equal to descendant objects 2 Adapted from Pearson Education, Inc.

3. Reprise: The ADT Heap Interface considered in Chapter 23 Listing 23-6 3 Adapted from Pearson Education, Inc.

4. Example 4 Adapted from Pearson Education, Inc.

5. Array to Represent a Heap Begin by using array to represent complete binary tree. Complete tree is full to its next-to-last level Leaves on last level are filled from left to right Locate either children or parent of any node by performing simple computation on node s number 5 Adapted from Pearson Education, Inc.

6. The steps in adding 85 to a maxheap 6 Adapted from Pearson Education, Inc.

7. A revision of the steps to avoid swaps 7 Adapted from Pearson Education, Inc.

8. An array representation of the steps 8 Adapted from Pearson Education, Inc.

9. An array representation of the steps 9 Adapted from Pearson Education, Inc.

10. RemoveMax 10 Adapted from Pearson Education, Inc.

11. Adding 20, 40, 30, 10, 90, and 70 11 Adapted from Pearson Education, Inc.

12. The steps in creating a heap of the entries 20, 40, 30, 10, 90, and 70 by using reheap 12 Adapted from Pearson Education, Inc.

13. The steps in creating a heap of the entries 20, 40, 30, 10, 90, and 70 by using reheap 13 Adapted from Pearson Education, Inc.

14. Figure 26-9 A trace of heap sort 14 Adapted from Pearson Education, Inc.

15. Figure 26-9 A trace of heap sort 15 Adapted from Pearson Education, Inc.

16. Figure 26-9 A trace of heap sort 16 Adapted from Pearson Education, Inc.

17. Efficiency 17 Adapted from Pearson Education, Inc.