a) 
struct heap{
         int maxsize;   //maximum size of the heap
         element[] table;  //array containing elements of the heap
         int last;   //array index of the last element
}
The root of the heap is always stored at array index 1. 
Then, for a given node at index i:
The parent of this node is stored at index: (i-2)/k + 1.  (...if i>1)
The j-th child of this node is stored at index: d(i-1) + j + 1.
Then every array index from 1 and last contains a heap element, and there is no wasted space in the array.


b)

int parent(i){
	return (i-2)/d + 1
}

int child(i, j){
	return k(i-1) + j + 1;
}

heap Insert(heap h, element x){
	i = h.last + 1;
	p = parent(i);
	while (i > 1) and (h.table[i] < h.table[p] do{
		swap(h.table[i], h.table[p]);
		i = p;
	}
	return h;
}



c)  

//this method returns array index of given element, starts search at given index of heap's array
int search (heap h, element x, int index){
	if (h.table[index]==x) return index;
	for (int m=1; m<=k; m++){  //iterating through each of this nodes k children
		c = child(index, m);
		if (c > last) return null;
		int address = search(x, c);
		if (address!=null) return address;  
	}
	return null;
}

int deleteElement(heap h, element x){
	int address = search(h, x, 1);
	if (address==null) return h;
	d = h.last-1;
	h.last=d;
	h.table[address] = h.table[d+1];
	i = address;
	c = child(i,1);
	while (c <= d){
		if (h.table[i] > h.table[c]) swap(h.table[i], h.table[c]);
		i = c;
		c = child(c,1);
	}
	return h;	
}



d)

list Heapsort(list L){
	h := emptyheap;
	for x from first to last element of L do
		h = insert(h,x);
	LL = emptylist;
	while not empty(h) do{
		LL = LL.root(h)
		h = delete(h, root(h));
	}
	return LL;
}