...

/

Solution Review: Convert Max-Heap to Min-Heap

Solution Review: Convert Max-Heap to Min-Heap

Take a look at the detailed solution review of the challenge given in the previous lesson.

Solution: Min heapify all parent nodes

Press + to interact
using System;
using System.Collections.Generic;
namespace chapter_8
{
class exercise_1
{
static void minHeapify(List<int> h, int i)
{
int lc = i * 2 + 1;
int rc = i * 2 + 2;
int imin = i;
if (lc < h.Count && (h[lc].CompareTo(h[imin]) < 0))
imin = lc;
if (rc < h.Count && (h[rc].CompareTo(h[imin]) < 0))
imin = rc;
if (i != imin)
{
int temp = h[i];
h[i] = h[imin];
h[imin] = temp;
minHeapify(h,imin);
}
}
static List<int> buildMinHeap(List<int> heapList)
{
for (int i = (heapList.Count - 1) / 2; i > -1; i--)
{
minHeapify(heapList, i);
}
return heapList;
}
static string convertMax(List<int> maxHeap)
{
string result = "";
maxHeap = buildMinHeap(maxHeap);
for (int i = 0; i < maxHeap.Count; i++)
{
if (i == maxHeap.Count - 1)
result += maxHeap[i].ToString();
else
result += maxHeap[i].ToString() + ",";
}
return result;
}
static void Main(string[] args)
{
List<int> heapList = new List<int>{ 9, 4, 7, 1, -2, 6, 5 };
Console.Write(convertMax(heapList));
return;
}
}
}
...