altai’s blog

 1: using System;

 2: using System.Collections.Generic;

 3: using System.Text;

 4:  

 5: namespace Halda

 6: {

 7: class Program

 8: {

 9: static void Main(string[] args)

 10: {

 11: int[] pole = { 1, 15, 2, 14, 3, 13, 4, 12, 5, 11, 6, 10, 7, 9, 0 };

 12:  

 13: pole = HaldaOperations.Instance.Build(pole, 14);

 14: HaldaOperations.Instance.Write(pole);

 15:  

 16: pole = HaldaOperations.Instance.DeleteMaximum(pole, 14);

 17: HaldaOperations.Instance.Write(pole);

 18:  

 19: pole = HaldaOperations.Instance.Add(pole, 8, 14);

 20: HaldaOperations.Instance.Write(pole);

 21: 

 22: Console.ReadKey();

 23: 

 24: }

 25: }

 26: }

 1: /// <summary>

 2: /// Deletes maximal item in heap

 3: /// </summary>

 4: /// <param name="heap">array of heap</param>

 5: /// <param name="size">size of heap</param>

 6: /// <returns>new heap, without max</returns>

 7: public int[] DeleteMaximum(int[] heap, int size)

 8: {

 9: if (heap.Length == 0)

 10: {

 11: Console.WriteLine("ERROR : Size is bigger than array length");

 12: return heap;

 13: }

 14:  

 15: int j, n, d; 

 16: //n - index of higher son

 17: //j - index of father

 18: //d - temporary int for swapping

 19: bool cont;

 20:  

 21: heap[0] = heap[size - 1];

 22: size--;

 23: j = 0;

 24: cont = (2 <= size);

 25: while (cont)

 26: {

 27: if (j == 0) { n = 1; } //array is indexed from 0

 28: else { n = 2 * j; }

 29:  

 30: if (n < size && heap[n + 1] > heap[n])

 31: n++; //n is index of higher son

 32:  

 33: if (heap[j] < heap[n])

 34: {

 35: d = heap[j];

 36: heap[j] = heap[n];

 37: heap[n] = d;

 38: 

 39: j = n;

 40: cont = (2 * j <= size);

 41: }

 42: else

 43: {

 44: cont = false;

 45: }

 46:  

 47: }

 48: return heap;

 49: }

 1: /// <summary>

 2: /// Adds item to heap

 3: /// </summary>

 4: /// <param name="heap">array of heap</param>

 5: /// <param name="data">data, that are you adding to heap</param>

 6: /// <param name="size">size of heap, before adding</param>

 7: /// <returns>new heap with added value</returns>

 8: public int[] Add(int[] heap, int data, int size)

 9: {

 10: if (heap.Length == size)

 11: {

 12: Console.WriteLine("ERROR : Heap is full");

 13: return heap;

 14: }

 15:  

 16: //j - index of son

 17: //p - index of parent

 18: //d - temporary int for swapping

 19: int j, p, d;

 20: //says if it'll continue with "upbubbling" new value

 21: bool cont;

 22: //you are adding, so increment size

 23: size++;

 24: //add avlue to the end of array(tree)

 25: heap[size - 1] = data;

 26: //index of added value

 27: j = size - 1;

 28: //if i'm not head of tree

 29: cont = j > 0;

 30:  

 31: while (cont)

 32: {

 33: //index of parent

 34: p = j / 2;

 35: 

 36: if (heap[j] > heap[p]) //son is bigger than parent, so change'em

 37: {

 38: //swap parent and son

 39: d = heap[j];

 40: heap[j] = heap[p];

 41: heap[p] = d;

 42: //now go one level higher

 43: j = p;

 44: //am i still not on the top???

 45: cont = j > 0;

 46: }

 47: else

 48: {

 49: cont = false;

 50: }

 51: }

 52: return heap;

 53: }