Citrix System Inc Interview Question
Software Engineer / Developers#include <iostream>
using namespace std;
int n;
void heapify(int a[], int i, int n)
{
int l=i*2,r=i*2+1,largest;
if(l<=n && a[l]<a[i])
largest = l;
else
largest = i;
if(r<=n && a[r]<a[largest])
largest = r;
if(largest!=i)
{
swap(a[i], a[largest]);
heapify(a,largest,n);
}
}
int main()
{
int a[] = {-1,5,2,4,7,1,9,3};
n=7;
for(int i=n/2;i>=1;i--)
{
heapify(a,i,n);
}
for(int i=1;i<=n;i++)
{
cout<<a[i]<<" ";
}
return 0;
}
def heapify(root, h, max_idx):
- ll March 12, 2011# no child
if (2*root+1) > max_idx: return
# has child
left = 2*root + 1
right = 2*root + 2
min_idx = root
if h[min_idx] > h[left]: min_idx = left
if right <= max_idx:
if h[min_idx] > h[right]: min_idx = right
if min_idx != root:
h[min_idx],h[root] = h[root],h[min_idx]
heapify(min_idx, h, max_idx)
return
def build_minheap(h):
n = len(h)
for idx in range(n-1,-1,-1): heapify(idx,h,n-1)
return h
if __name__ == '__main__':
H = [3,4,599,-1,-45,0,456,7,344]
H = build_minheap(H)
print H