Implemented a heap but sill time exceeded!


  • 0
    A

    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>();
    		ListNode head = new ListNode(-1);
    		ListNode tmp = head;
    		for (int i = 0; i < lists.size(); i++) {
    			ListNode n = lists.get(i);
    			if (n != null) {
    				addHeap(pointers, n);
    			}
    		}
    		while (true) {
    			if (pointers.size() == 0) {
    				break;
    			}
    			ListNode ptr = delHeap(pointers);		
    			tmp.next = ptr;
    			tmp = tmp.next;
    			ListNode next = ptr.next;
    			if (next != null) {
    				addHeap(pointers, next);
    			}
    		}
    		return head.next;
    	}
    
    	
    	// algorithm is wrong, check heap sort again
    	public void addHeap(ArrayList<ListNode> pointers, ListNode n) {
    		pointers.add(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;
            }
    		pointers.add(0, pointers.remove(pointers.size()-1));
    		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;
    	}

  • 1
    S

    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;
    		public LeastHeap(List<ListNode> headList){
    			this.capacity = headList.size();
    			content = new ListNode[this.capacity];
    			int count=0;
    			for(ListNode headI : headList){
    				if (headI!=null){
    					content[count] = headI;
    					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){
    		ListNode preHeader = new ListNode(0);
    		ListNode itr = preHeader;
    		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);
    			}
    		}
    		return preHeader.next;
    	}

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.