2 replies to this topic

[aszaszin]

To all user....

plzzzz you may help me to have a program about priority scheduling using c# language????

[zoranh]

Priority is easily implemented using the heap structure (Wikipedia Heap Data Strucutre). That is method-of-choice in many applications.

Heap has property that first element is always the smallest one (or largest if you invert comparison logic).

I can post you the working code that I once wrote, when I get back home.

[zoranh]

Here is the heap data structure implemented in C#:

using System;
using System.Collections.Generic;
using System.Text;

namespace Data
{
    /// <summary>
    /// Implements heap data structure
    /// </summary>
    public class Heap<T>
    {

        /// <summary>
        /// Default public constructor.
        /// If this constructor is used then generic type T 
        /// must implement IComparable<T> interface.
        /// </summary>
        public Heap()
        {
            _array = new T[0];
        }

        /// <summary>
        /// Public constructor which sets comparer object.
        /// </summary>
        /// <param name="comp">Comparer used to compare elements in the heap.</param>
        public Heap(IComparer<T> comp): this()
        {
            _comparer = comp;
        }

        /// <summary>
        /// Increases size of the heap so that at least <paramref name="size"/>
        /// elements can be inserted.
        /// </summary>
        /// <param name="size">Required number of elements that heap 
        /// should be capable to receive.</param>
        private void EnsureSize(int size)
        {

            if (AllocatedSize < size)
            {
                
                int newSize = AllocatedSize;
                
                if (newSize == 0)
                    newSize = 1;

                while (newSize < size)
                    newSize += newSize;

                Array.Resize<T>(ref _array, newSize);

            }
        }

        /// <summary>
        /// Gets total allocated size of the internal array.
        /// </summary>
        public int AllocatedSize
        {
            get
            {
                return _array.Length;
            }
        }

        /// <summary>
        /// Gets total number of items currently stored in this heap.
        /// </summary>
        public int Count
        {
            get
            {
                return _count;
            }
        }

        /// <summary>
        /// Inserts new element to the heap and rearranges existing elements
        /// so that the heap property remains.
        /// </summary>
        /// <param name="item">Item inserted to the heap.</param>
        public void Insert(T item)
        {

            EnsureSize(this.Count + 1);

            int pos = _count++;
            bool exchanged = true;

            _array[pos] = item;

            while (exchanged && pos > 0)
            {

                int newPos = ((pos + 1) >> 1) - 1;

                if (Compare(pos, newPos) < 0)
                    Exchange(pos, newPos);
                else
                    exchanged = false;

                pos = newPos;

            }

        }

        /// <summary>
        /// Removes smallest element from the heap.
        /// </summary>
        /// <returns>Item remvoed from the heap.</returns>
        /// <exception cref="System.InvalidOperationException">Heap is empty and no element can be removed from it.</exception>
        public T Remove()
        {

            if (_count == 0)
                throw new System.InvalidOperationException("Cannot remove item from empty heap.");

            int pos = 0;
            T result = _array[0];

            _array[0] = _array[--_count];

            while (pos < _count)
            {

                int left = ((pos + 1) << 1) - 1;
                int right = left + 1;

                if (left >= _count)
                    pos = _count;   // Item has no leaves
                else if (right >= Count)
                {
                    // There is only the left leaf
                    if (Compare(pos, left) <= 0)
                    {   // Current element is smaller than the leaf so remains at current position
                        pos = _count;
                    }
                    else
                    {   // Left leaf is smaller than current element, so element descends to leaf's position
                        Exchange(pos, left);
                        pos = left;
                    }

                }
                else
                {   // There are both leaves, now compare this element with smaller of the two

                    int newPos = left;
                    if (Compare(right, left) < 0)
                        newPos = right;

                    if (Compare(newPos, pos) < 0)
                    {   // Smaller leaf is smaller than current element - exchange them and descent to new position
                        Exchange(pos, newPos);
                        pos = newPos;
                    }
                    else
                    {   // Current element does not violate the heap property so descent terminates
                        pos = _count;
                    }
                }

            }

            CompactHeap();

            return result;

        }

        /// <summary>
        /// Compares elements on specified positions in the internal array.
        /// </summary>
        /// <param name="pos1">Position of the first element in the array.</param>
        /// <param name="pos2">Position of the second element in the array.</param>
        /// <returns>Returns -1 if element at position <paramref name="pos1"/> is smaller than
        /// element at position <paramref name="pos2"/>.
        /// Returns +1 if element at position <paramref name="pos1"/> is greater than
        /// element at position <paramref name="pos2"/>.
        /// Returns 0 if two elements are equal.</returns>
        private int Compare(int pos1, int pos2)
        {

            int result = 0;

            if (_comparer != null)
            {
                result = _comparer.Compare(_array[pos1], _array[pos2]);
            }
            else if (_array[pos1] is IComparable<T>)
            {
                IComparable<T> c = _array[pos1] as IComparable<T>;
                result = c.CompareTo(_array[pos2]);
            }
            else
            {
                throw new System.InvalidOperationException("Unable to compare elements in heap.");
            }

            return result;

        }

        /// <summary>
        /// Reduces size of the internal array if number of items stored in it is small
        /// compared to total allocated size of the array.
        /// </summary>
        private void CompactHeap()
        {

            if (_count < _array.Length / 10)
            {

                int newSize = 1;

                while (newSize < _count)
                    newSize = newSize >> 1;

                Array.Resize<T>(ref _array, newSize);

            }
            
        }

        /// <summary>
        /// Exchanges values at the two positions of the array.
        /// </summary>
        /// <param name="pos1">Position of the first element which exchanges place.</param>
        /// <param name="pos2">Position of the second element which exchanges place.</param>
        private void Exchange(int pos1, int pos2)
        {
            T tmp = _array[pos1];
            _array[pos1] = _array[pos2];
            _array[pos2] = tmp;
        }

        /// <summary>
        /// Total number of elements stored in heap.
        /// </summary>
        public int _count;

        /// <summary>
        /// Array containing the heap structure.
        /// </summary>
        private T[] _array;

        /// <summary>
        /// Comparer used to compare elements in heap.
        /// </summary>
        private IComparer<T> _comparer;

    }
}