Tuesday, October 29, 2013

Inserting an element into a heap

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);
      }
}

Struct in C#

A struct type is a value type that is typically used to encapsulate small groups of related variables, such as the coordinates of a rectangle or the characteristics of an item in an inventory. The following example shows a simple struct declaration:

public struct Book
{
    public decimal price;
    public string title;
    public string author;
}



Structs can also contain constructors, constants, fields, methods, properties, indexers, operators, events, and nested types, although if several such members are required, you should consider making your type a class instead.
Structs can implement an interface but they cannot inherit from another struct. For that reason, struct members cannot be declared as protected.
                                                                                                                                   

Using Struct
The struct type is suitable for representing lightweight objects such as Point, Rectangle, and Color. Although it is just as convenient to represent a point as a class with Auto-Implemented Properties, a struct might be more efficient in some scenarios. For example, if you declare an array of 1000 Point objects, you will allocate additional memory for referencing each object; in this case, a struct would be less expensive. Because the .NET Framework contains an object called Point, the struct in this example is named "CoOrds" instead.

public struct CoOrds
{
    public int x, y;
 
    public CoOrds(int p1, int p2)
    {
        x = p1;
        y = p2;
    }
}



It is an error to define a default (parameterless) constructor for a struct. It is also an error to initialize an instance field in a struct body. You can initialize struct members only by using a parameterized constructor or by accessing the members individually after the struct is declared. Any private or otherwise inaccessible members can be initialized only in a constructor.

When you create a struct object using the new operator, it gets created and the appropriate constructor is called. Unlike classes, structs can be instantiated without using the new operator. In such a case, there is no constructor call, which makes the allocation more efficient. However, the fields will remain unassigned and the object cannot be used until all of the fields are initialized.

There is no inheritance for structs as there is for classes. A struct cannot inherit from another struct or class, and it cannot be the base of a class. Structs, however, inherit from the base class Object. A struct can implement interfaces, and it does that exactly as classes do.
You cannot declare a class using the keyword struct. In C#, classes and structs are semantically different. A struct is a value type, while a class is a reference type.

Unless you need reference-type semantics, a small class may be more efficiently handled by the system if you declare it as a struct instead.

Linq to get Duplicate Values from a list

void Main()
{
       //int[] listOfItems = new[] { 4, 2, 3, 1, 6, 4, 3 };
       List<Hotel> listOfItems = new List<Hotel>();
       listOfItems.Add(new Hotel(){ name="Hotel1"});
       listOfItems.Add(new Hotel(){ name="Hotel2"});
       listOfItems.Add(new Hotel(){ name="Hotel3"});
       listOfItems.Add(new Hotel(){ name="Hotel3"});
       listOfItems.Add(new Hotel(){ name="Hotel4"});
       listOfItems.Add(new Hotel(){ name="Hotel1"});
       listOfItems.Add(new Hotel(){ name="Hotel4"});
      
       var duplicates = listOfItems
           .GroupBy(i => i.name)
           .Where(g => g.Count() > 1)
           .Select(k => k.Key);
      
       Console.WriteLine(duplicates.Count());
      
       foreach (var d in duplicates)
           Console.WriteLine(d);
}

class Hotel
{
public string name;
}



Linq - Group By Finding Duplicates


This post is a little snippet on using Linq to find duplicates in a list of objects where a specific property of the object is used to find the duplicates. In this particular example, the objects are Lessons and in addition to other properties each lesson has a AddedDate property and what we need to do is find all lessons where the AddedDate is a duplicate of another lesson.

In order to solve this we use Group By and we group by the AddedDate property and if any group has a count greater than 1, it is a duplicate and we need to get those.

For test purposes, I've defined a variable called testDateAndTime that is assigned to the current DateTime.
And then at the time of initializing the Lesson instances, I've assigned two lessons the same date and time using this variable.
The two lessons (as shown in the code listing below) are:
  1. Preposition / Phrasal Verb
  2. German Verbs in the Present Tense

class Program
  {
    static void Main(string[] args)
    {
      var testDateAndTime = DateTime.Now;

      var lessons = new Lesson[] {
        new Lesson { Title="Verb Tense", Subject="English", AddedDate = DateTime.Now.AddMinutes(1)},
        new Lesson { Title="Conditionals", Subject="English", AddedDate = DateTime.Now.AddDays(2)},
        new Lesson { Title="Gerunds and Infinitives", Subject="English", AddedDate = DateTime.Now.AddDays(3)},
        new Lesson { Title="Vocabulary", Subject="English", AddedDate = DateTime.Now.AddDays(4)},
        new Lesson { Title="Preposition / Phrasal Verb", Subject="English", AddedDate = testDateAndTime},
        new Lesson { Title="Greetings", Subject="German", AddedDate = DateTime.Now.AddMinutes(5)},
        new Lesson { Title="Personal pronouns", Subject="German", AddedDate = DateTime.Now.AddDays(6)},
        new Lesson { Title="Introduction to nouns and gender", Subject="German", AddedDate = DateTime.Now.AddDays(7)},
        new Lesson { Title="Two important verbs", Subject="German", AddedDate = DateTime.Now.AddDays(8)},
        new Lesson { Title="German Verbs in the Present Tense", Subject="German", AddedDate = testDateAndTime}
      };

      var groupedLessons = from l in lessons
                           group l by l.AddedDate into g
                           where g.Count() > 1
                           select new { AddedDate = g.Key, Lessons = g };

      foreach (var k in groupedLessons)
      {
        Console.WriteLine("Added Date: " + k.AddedDate);
        foreach (var l in k.Lessons)
        {
          Console.WriteLine("\t Lesson Title: " + l.Title);
        }
      }
    }
  }

  public class Lesson
  {
    public string Title { get; set; }
    public string Subject { get; set; }
    public DateTime AddedDate { get; set; }
  }

If you run this program you'll see the following output, which is what you'd expect.

Added Date: 2/2/2011 8:08:59 AM
         Lesson Title: Preposition / Phrasal Verb
         Lesson Title: German Verbs in the Present Tense