Heaps

An improve to BST

https://talks.obedmr.com/

Let's start with the Priority Queues

A priority queue is a data structure that allows at least the following two operations:

  • insert, which does the obvious thing;
  • deleteMin, which finds, returns, and removes the minimum element in the priority queue

So, now, Heaps

  • A heap is a type of data structure. One of the interesting things about heaps is that they allow you to find the largest (or smallest) element in the heap in time.

  • Remember Priority Queues?

    • A max (or min) heap is a complete (or almost complete) binary tree such that the data stored in each node is greater (or smaller) than the data stored in its children, if any

  • What's the similarity you see between heaps and priority queues?

Binary Heaps

The binary heaps have 2 properties:

  • Structure property
  • A Heap-Order property

As with AVL trees (remember the invariants?), an operation on a heap can destroy one of the properties, so a heap operation must not terminate until all heap properties are in order. This turns out to be simple to do.

Binary Heaps - Structure property

A heap is a binary tree that is completely filled, with the possible exception of the bottom level, which is filled from left to right. Such a tree is known as a complete binary tree.

A complete binary tree of height has between and nodes. This implies that the height of a complete binary tree is logN , which is clearly .

Important Observation: Because a complete binary tree is so regular, it can be represented in an array and no links (or pointers) are necessary.

Binary Heaps - Heap-Order property

  • Allows operations to be performed quickly
  • The smallest element should be at the root
  • If we consider that any subtree should also be a heap, then any node should be smaller than all of its descendants.

Since a heap is a Complete Binary Tree ...

In the array representation, the element at position k represents a node in the tree whose child nodes will be at positions and of the array

Binary Heaps: Array Implementation

Consider the following rules:

So, let's think about it

  • Every ordered list is a heap
  • Any list can be converted into a heap and from there, the corresponding applications can be obtained.
  • Which of the following lists are a heap?
8, 3, 2, 1, 2, 1
1, 2, 3, 4, 5, 6, 7, 8
5, 8, 9, 7, 5, 4
3, 4, 3, 4, 4, 3, 5

Basic Operations: insert

  • To insert an element X into the heap, we create a hole in the next available location, since otherwise, the tree will not be complete.
  • If X can be placed in the hole without violating heap order, then we do so and are done.
  • Otherwise,
    • We slide the element that is in the hole’s parent node into the hole, thus bubbling the hole up toward the root. We continue this process until X can be placed in the hole.
  • This general strategy is known as a percolate up; the new element is percolated up the heap until the correct location is found.

insert(20)

insert(20)

insert(20)

Verify with the parent (17)

insert(20)

Verify with the parent (28)

insert(20)

DONE!

insert(15)

insert(15)

insert(15)

Verify with the parent (19)

insert(15)

DONE!

Basic Operations delete

Let's consider the case of removing the root

  • When the minimum is removed, a hole is created at the root.
  • Since the heap now becomes one smaller, it follows that the last element X in the heap must move somewhere in the heap.
  • If X can be placed in the hole, then we are done.
  • This is unlikely, so we slide the smaller of the hole’s children into the hole, thus pushing the hole down one level.
  • We repeat this step until X can be placed in the hole.
  • Thus, our action is to place X in its correct spot along a path from the root containing minimum children
    This general strategy is known as a percolate down.

Let's Code

Consider the implementation of heaps from Geeks for Geeks

  • In your own words, explain what's the function of the heapify(int i) function
  • Implement the find(int value) function
  • Implement the delete(int value) function

Resources and Credits

This material is genereated thanks to some extracts from following resources:

  • González, Luis Humberto. Abstraccion de Datos
  • Allen Weiss, Mark. Data Structures and Algorithm Analysis in C++
  • Google-generated code with AI Overview

Thanks