Skip to main content

Inserting an element into a heap

Image
By

Inserting an element into a heap     

In this article we examine the idea laying in the foundation of the heap data structure. We call it sifting, but you also may meet another terms, like "trickle", "heapify", "bubble" or "percolate".

Insertion algorithm

Now, let us phrase general algorithm to insert a new element into a heap.

  1. Add a new element to the end of an array;
  2. Sift up the new element, while heap property is broken. Sifting is done as following: compare node's value with parent's value. If they are in wrong order, swap them.

Example

Insert -2 into a following heap:

Insert a new element to the end of the array:

In the general case, after insertion, heap property near the new node is broken:

To restore heap property, algorithm sifts up the new element, by swapping it with its parent:

Now heap property is broken at the root node:

Keep sifting:

Heap property is fulfilled, sifting is over.

Source heap

After -2 insertion

Complexity analysis

Complexity of the insertion operation is O(h), where h is heap's height. Taking into account completeness of the tree, O(h) = O(log n), where n is number of elements in a heap.

Code snippets

Java implementation

public class BinaryMinHeap {     

public void insert(int value) {

            if (heapSize == data.length)

                  throw new HeapException("Heap's underlying storage is overflow");

            else {

                  heapSize++;

                  data[heapSize - 1] = value;

                  siftUp(heapSize - 1);

            }

      }    

 

      …

     

private void siftUp(int nodeIndex) {

            int parentIndex, tmp;

            if (nodeIndex != 0) {

                  parentIndex = getParentIndex(nodeIndex);

                  if (data[parentIndex] > data[nodeIndex]) {

                        tmp = data[parentIndex];

                        data[parentIndex] = data[nodeIndex];

                        data[nodeIndex] = tmp;

                        siftUp(parentIndex);

                  }

            }

      }

}

C++ implementation

void BinaryMinHeap::siftUp(int nodeIndex) {

      int parentIndex, tmp;

      if (nodeIndex != 0) {

            parentIndex = getParentIndex(nodeIndex);

            if (data[parentIndex] > data[nodeIndex]) {

                  tmp = data[parentIndex];

                  data[parentIndex] = data[nodeIndex];

                  data[nodeIndex] = tmp;

                  siftUp(parentIndex);

            }

      }

}

 

void BinaryMinHeap::insert(int value) {

      if (heapSize == arraySize)

            throw string("Heap's underlying storage is overflow");

      else {

            heapSize++;

            data[heapSize - 1] = value;

            siftUp(heapSize - 1);

      }

}

DISCLAIMER ========== This e-mail may contain privileged and confidential information which is the property of Persistent Systems Ltd. It is intended only for the use of the individual or entity to which it is addressed. If you are not the intended recipient, you are not authorized to read, retain, copy, print, distribute or use this message. If you have received this communication in error, please notify the sender and delete all copies of this message. Persistent Systems Ltd. does not accept any liability for virus infected mails.

Labels:

Comments

Post a Comment

Popular posts from this blog

WPF-MVVM: RelayCommand Implementation

By
In WPF if we are implementing MVVM pattern then we need to play with Command rather than Events. You can use ICommand interface to create each command class. Implementation of ICommand in a class gives you CanExecute(), Execute() methods which take part in the action performed by Command.   Rather than making Command Class for each Command we can implement a generic Relay Command to get Command. Below is a RelayCommand class that we will implement.   ///   <summary>      ///  To register commands in MMVM pattern      ///   </summary>      class   RelayCommands  :  ICommand     {          readonly   Action < object > _execute;          readonly   Predicate < object > _canExecute;  ...
Post a Comment
Read more

iOS Dev: Encryption in Objective-C

By
Hello Friends: In this Article/Post, I introduced the one encryption technique in Objective-C.  Encryption Component Features in all  Symmetric Encryption: AES, Blowfish, Twofish, RC2, ARC4, DES, 3DES, PBES1, PBES2. Hash Algorithms :  SHA-1 , SHA256, SHA384, SHA512, MD2, MD4, MD5, HAVAL. Hash Algorithms: RIPEMD128, RIPEMD160, RIPEMD256, RIPEMD320. Encoding: Base64, hex, quoted-printable,  URL-encoding . HMAC with any supported hash algorithm: HMAC-MD5,  HMAC-SHA1 , etc. Password-based Key Derivation Functions: PBKDF1, PBKDF2 PKCS7 -- P7S and P7M creation, decryption, verification. Public key encryption/decryption with digital certificates. Digital signature creation/verification with digital certificates. Bzip2 in-memory compression. Encrypt / decrypt strings or byte data. Return encrypted data as Base64, quoted-printable, or hex-encoded strings. Hash strings or binary data using SHA1, MD2, MD5, HAVAL, SHA384, or SHA512. Public-key encryp...
1 comment
Read more

Reactive Extensions (Rx)

By
Reactive Extensions (Rx) What is Rx Rx is a library for composing asynchronous and event-based programs using observable collections. Using Rx, developers represent asynchronous data streams with Observables, query asynchronous data streams using LINQ operators, and parameterize the concurrency in the asynchronous data streams using Schedulers. Simply put, Rx = Observables + LINQ + Schedulers. The Reactive Extensions (Rx) is a library for composing asynchronous and event-based programs using observable sequences and LINQ-style query operators. Whether you are authoring a traditional desktop or web-based application, you have to deal with asynchronous and event-based programming from time to time. Desktop applications have I/O operations and computationally expensive tasks that might take a long time to complete and potentially block other active threads. Furthermore, handling exceptions, cancellation, and synchronization is difficult and error-prone. Thr...
Post a Comment
Read more