Insertion of an Element in a Heap
- An element is initially inserted as the last child of the heap.
- On insertion, the heap remains a complete binary tree, but the order property may be violated.
- We have to perform a series of operations to move the element up from the last position until either it ends up in a position where the order property is satisfied or we hit the root node.
- In this tutorial, we refer to this process as the reheapify upward operation.
Algorithm
ReheapifyUpward(heap,start)
Here heap is a linear array and start is the index of the element from where the reheapifyupward operation is to start. It uses parent as the index of the parent node in the heap.
Begin if heap[start] is not root node then if (heap[parent]<heap[start]) then swap heap[parent] and heap[start] call ReheapifyUpward(heap,parent) endif endif end
C/C++ implementation
.cf { font-family: Lucida Console; font-size: 9pt; color: black; background: white; } .cl { margin: 0px; } .cb1 { color: green; } .cb2 { color: blue; }
void reheapifyUpward(int heap[],int start)
{
int temp, parent;
if(start>1)
{
parent=start/2;
if(heap[parent]<heap[start])
{
temp = heap[start];
heap[start] = heap[parent];
heap[parent] = temp;
reheapifyUpward(heap,parent);
}
}
}
|
|
- Deleting an Element from a Heap
Deleting an Element from the Heap Deletion always occurs at the root of the heap. If we delete the root element it creates a hole or vacant space at the root position. Because the heap must be complete, we fill the hole with the last element of the heap. Although the heap becomes complete, i.e. [...]...
- Deleting an Element from a Doubly Linked List
To delete an element from the list, first the pointers are set properly and then the memory occupied by the node to be deleted is deallocated (freed). Deletion in the list can take place at the following positions. At the beginning of the list At the end of the list After a given element Before [...]...
- Deleting an Element from a Linear Linked List
To delete an element from the list, first the pointers are set properly and then the memory occupied by the node to be deleted is deallocated (freed). This tutorial covers the deletion of a node from the following three positions: At the beginning of the list At the end of the list After a given [...]...
- Insertion in a Linear Linked List
To insert an element in the list, the first task is to create a new node, assign the element to be inserted to the info field of the node, and then place the new node at the appropriate position by adjusting the appropriate pointers. Insertion in the list can take place at the following positions: [...]...
- Heaps
A heap is a binary tree that satisfies the following properties: Shape property Order property By the shape property, we mean that a heap must be a complete binary tree. A complete binary tree has all its levels filled, except possibly for the last, where the leaves must be located as far to the left [...]...