Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- * DArySimpleIntegerMaximumHeap.cs
- * 04.09.11
- * 21:11
- *
- * Programmers :
- * Miky Lestat AKA m1o2
- * Course : Data Structure
- * lecturer : Amir Robinshtain
- *
- * a simple implementaion of D-ary Heaps using int arrays.
- *
- */
- using System;
- namespace DataStructure_Heaps_Project
- {
- public class DArySimpleIntegerHeap : ICountableHeap
- {
- public int Root { get; set; } // will holds the Root of the heap. for example, if the heap is a Max heap then, it will hold the max
- public int Degree { get { return _degree; } } // a property holds the degree of the heap.
- public int[] Heap { get; set; } // an array that contain all of the heap elements.
- protected int Top { get; set; } // an indicator ( index ) for the index of the last elements ( leaf ) in the heap ( array )
- public int SwapsCount{ get; set; } // will hold the number of swaps done in Build-Heap operation
- public int ComparisonsCount{ get; set; } // will hold the number of comaprisons done in Build-Heap operation.
- int _degree; // holds the degree
- // if top numbers.length-1 isn't the last element in the array, then, we give us the top.
- public DArySimpleIntegerHeap( int[] numbers, int top, int degree = 2)
- {
- initialize(numbers, top, degree);
- }
- public DArySimpleIntegerHeap(int[] numbers, int degree = 2)
- {
- initialize(numbers, numbers.Length, degree);
- }
- // initialize all the variables of the Heap implementation and also CALL build-heap
- protected void initialize(int[] numbers, int top, int degree)
- {
- if (degree < 2)
- throw new DegreeSmallerThanTwoException();
- this._degree = degree;
- Heap = (int[])numbers.Clone(); // shallow copy ( copies only the references )
- Top = top;
- int swaps = 0, comparisons = 0; // for counting the number of swapns and number of comprisons.
- Build_Heap( out comparisons, out swaps ); // buildheap
- ComparisonsCount = comparisons;
- SwapsCount = swaps;
- }
- public void Build_Heap(out int comparisons, out int swaps)
- {
- // initialize variables.
- swaps = 0;
- comparisons = 0;
- /*
- * we will start at the parent of the last leaf in the array. for example, in heap with degree 2 we will start at [n/2]
- * */
- for (int index = ParentIndex( Top-1 ); index >= 0; --index)
- {
- int s = 0;
- int c = 0;
- HeapifyDown(index, out c, out s ); // heapify-Down
- comparisons += c;
- swaps += s;
- }
- }
- // in this project we did not use this method.
- public void HeapifyUp(int current, out int comparisons, out int swaps)
- {
- swaps = 0;
- comparisons = 0;
- if (0 == current) // we reached the root
- return;
- int father = ParentIndex(current);
- ++comparisons;
- if (Heap[father] < Heap[current]) // if the child bigger than the father
- {
- int s = 0;
- int c = 0;
- //++swaps;
- swaps += 3;
- exchange(current, father); // swap the values.
- HeapifyUp(father, out c, out s); // recursivly heapify up
- comparisons += c;
- comparisons += s;
- }
- }
- public void HeapifyDown(int current, out int comparisons, out int swaps)
- {
- swaps = 0;
- comparisons = 0;
- int max = current;
- int child = 0;
- /*
- * for every child, and while childs exists, check if the children is smaller than theire fathers.
- * if a child isn't smaller or equal to his father, and he is the bigger child ( holds the bigger key value of his brothers ) then swap it with his father
- * and then heapifyDown.
- * */
- for (int index = 0; child < Top && index < Degree; ++index)
- {
- child = Ichild(current, index + 1); // we could iterate as child += 1, but I think this way is clearer.
- if (child < Top) // I don't like to use break. if there isn't any child anymore then don't do nothing and it also will be the last operation
- {
- ++comparisons;
- if (child < Top && Heap[child] > Heap[max]) // find the biggest child
- max = child;
- }
- }
- if (max != current) // if there is a child that is bigger than his father
- {
- int c = 0;
- int s = 0;
- //++swaps;
- swaps += 3;
- exchange(current, max); // exchange ( swap ) the child with his father, then heapifyDown
- HeapifyDown(max, out c, out s );
- swaps += s;
- comparisons += c;
- }
- }
- public int ParentIndex(int child)
- {
- return (int)Math.Floor((double)((child - 1) / Degree)); // getting the parent index of the givern child.
- }
- public int Ichild(int parent, int child) // getting the I child of the fiver parent.
- {
- return (Degree * parent) + child; //
- }
- public int ExtractRoot(out int comparisons, out int swaps )
- {
- comparisons = 0;
- swaps = 0;
- int root;
- if (0 == Top)
- throw new HeapIsEmptyException();
- //+swaps;
- swaps += 3;
- exchange(0, Top-1); // exchange the max with the last leaf.
- int s = 0;
- int c = 0;
- --Top;
- HeapifyDown(0, out c, out s ); // heapifyDown the root that now holds the key of the last leaf
- comparisons += c;
- swaps += s;
- root = Heap[Top]; //
- return root; // return the deleted root
- }
- protected void exchange(int a, int b)
- {
- int temp = Heap[a];
- Heap[a] = Heap[b];
- Heap[b] = temp;
- }
- /**
- * a sorting method using HeapSort.
- * it takes a numbers array ( , 2 variables for counting comparisons and swaps ) and the degree of the heap.
- * the method will sort the array using heap sort.
- * first of all it will build a heap, then it will call extract max till we sort all the array.
- * */
- public static void Sort(int[] numbers, out int comparisons, out int swaps, int degree = 2)
- {
- int s = 0;
- int c = 0;
- DArySimpleIntegerHeap heap = new DArySimpleIntegerHeap(numbers, degree); // building the heap.
- comparisons = heap.ComparisonsCount; // how many comparisons there was in Build-Heap operations
- swaps = heap.SwapsCount; // how many swaps there was in Build-Heap operations
- for (int index = 0; index < numbers.Length; ++index)
- {
- numbers[numbers.Length - 1 - index] = heap.ExtractRoot( out c, out s ); // get the extracted max and put it in the end of the array
- comparisons += c;
- swaps += s;
- }
- //swaps *= 3;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
