# Implemented a heap but sill time exceeded!

• I implemented a min heap to record the least element. But still get a time exceeded error.
Could you point my error ?

``````public ListNode mergeKLists(List<ListNode> lists) {
ArrayList<ListNode> pointers = new ArrayList<ListNode>();
for (int i = 0; i < lists.size(); i++) {
ListNode n = lists.get(i);
if (n != null) {
}
}
while (true) {
if (pointers.size() == 0) {
break;
}
ListNode ptr = delHeap(pointers);
tmp.next = ptr;
tmp = tmp.next;
ListNode next = ptr.next;
if (next != null) {
}
}
}

// algorithm is wrong, check heap sort again
public void addHeap(ArrayList<ListNode> pointers, ListNode n) {
if (pointers.size() <= 1) {
return;
}
int i = pointers.size()-1;
while( i >= 0 )
{
ListNode cur = pointers.get(i);
ListNode par;
int pos = i;
if (i%2 == 0 && i/2-1 >= 0)
{
par = pointers.get(i/2-1);
if(cur.val < par.val)
{
pointers.set(i/2-1, cur);
pointers.set(i, par);
i = i/2-1;
}
else {
break;
}
}
else
{
par = pointers.get(i/2);
if(cur.val < par.val)
{
pointers.set(i/2, cur);
pointers.set(i, par);
i = i/2;
}
else {
break;
}
}
}
}
public ListNode delHeap(ArrayList<ListNode> pointers) {
ListNode res = pointers.remove(0);
if(pointers.size() <= 1)
{
return res;
}
int i = 0;
while(2*i+1 < pointers.size())
{
ListNode cur = pointers.get(i);
int pos = i;
// find the smaller one
ListNode smaller = null;
if(2*i+1 < pointers.size())
{
if(2*i + 2 < pointers.size())
{
if(pointers.get(2*i+2).val < pointers.get(2*i+1).val)
{
smaller = pointers.get(2*i+2);
pos = 2*i+2;
}
else
{
smaller = pointers.get(2*i+1);
pos = 2*i+1;
}
}
else
{
smaller = pointers.get(2*i+1);
pos = 2*i+1;
}
}
if(smaller.val < cur.val)
{
pointers.set(i, smaller);
pointers.set(pos,cur);
i = pos;
}
else
{
break;
}
}
return res;
}``````

• Here is my solution for your compare. Basically I have implemented a LeastHeap that keeping the header of each array. Always take out the least as next and insert the next of the ranked node to the heap. Code is a little bit verbose but idea is simple and almost the same as your idea.

It only takes 230ms for my submission which is a very quick one in all results implemented in Java. I recommend you not use ArrayList<ListNode> but implement your own Heap or find other collections container dedicated to support heap as the ArrayList may possibly gives you overhead/API that you don't need.

``````public class MergeKSortedList {
static public class LeastHeap{
int capacity;
int size;
ListNode[] content;
content = new ListNode[this.capacity];
int count=0;
int itrId = count;
while(itrId!=0){
int parentId = (itrId-1)/2;
if (content[parentId].val>content[itrId].val){
ListNode parentNode = content[parentId];
content[parentId]= content[itrId];
content[itrId] = parentNode;
}
itrId = parentId;
}
count++;
}
}
size=count;
}

public void insert(ListNode newNode){
if (newNode!=null){
size=size+1;
int itrId = size-1;
content[itrId] = newNode;
while(itrId!=0){
int parentId = (itrId-1)/2;
if (content[parentId].val>content[itrId].val){
ListNode parentNode = content[parentId];
content[parentId]= content[itrId];
content[itrId] = parentNode;
}
itrId = parentId;
}
}
}

public ListNode popLeast(){
ListNode result=null;
if (size>=1){
result = content[0];
content[0] = content[size-1];
size=size-1;
int itrId=0;
while(itrId<(size)/2){
int leftChildId = itrId*2+1;
int rightChildId = (itrId*2+2<size)?itrId*2+2:itrId*2+1;
if (content[leftChildId].val > content[rightChildId].val){
if (content[itrId].val>content[rightChildId].val){
ListNode parentNode = content[rightChildId];
content[rightChildId]=content[itrId];
content[itrId]=parentNode;
itrId = rightChildId;
}
else{
itrId=size-1;
}
}else{
if (content[itrId].val>content[leftChildId].val){
ListNode parentNode = content[leftChildId];
content[leftChildId]=content[itrId];
content[itrId]=parentNode;
itrId = leftChildId;
}
else{
itrId=size-1;
}
}
}
}
return result;
}

public void displayHeap(){
for (int i=0;i<size;i++)
{
System.out.print(content[i].val+" ");
}
System.out.println();
}
}

public ListNode mergeKSortList(List<ListNode> lists){
LeastHeap nodeItr = new LeastHeap(lists);
while (nodeItr.size!=0){
ListNode cur = nodeItr.popLeast();
if (cur!=null){
itr.next = cur;
itr = itr.next;
nodeItr.insert(cur.next);
}
}