首页 > 试题广场 >

设计接口并且实现一个多线程安全的堆,并且要求可以删除堆中任意

[问答题]
设计接口并且实现一个多线程安全的堆,并且要求可以删除堆中任意元素(非堆顶元素),要求尽量高效,假设已有标准的mutex实现可以使用。
deleteElement(int[] heap, int index, int len) {    mutex.lock();
    heap[index] = heap[len-1];
    len--;
    while(2*index + 1 < len && (heap[index] > heap[2*index+1]|| heap[index] > heap[2*index +2])) {
         int swapi = heap[2*index+1] < heap[2*index +2]) ? 2*index+1 : 2*index+2;
          swap(heap,index,swapi);
         index = swapi;
    }
    mutex.unlock();
}

发表于 2017-07-22 15:06:20 回复(3)
各位大神,这里的堆指的是 大根堆、小根堆 的那个(heap),还是 堆栈 的那个 堆(stack)啊?
也就是我要不要有重建大根堆或小根堆的操作?
发表于 2017-08-24 11:12:25 回复(3)
import java.util.Stack;
//单例模式的 栈
public synchronized class SyncStack{
    volatile private Stack<Object> stack = new Stack<>();
    private SyncStack(){
    }

    public Stack<Object> getStack(){
        return this.stack;
    }
    
    public Object getElement(int index){
        if(index<0 ||index > (this.stack.size()-1){
            return null;
        }
        
        this.stack.get(index);
    }

    public void removeELement(int index){
        if(index<0 || index > (this.stack.size()-1)){
            return;
        }
        this.stack.remove(index);
    }
}

发表于 2017-08-23 20:57:15 回复(2)
我选择放弃
发表于 2018-05-25 22:14:42 回复(2)
我想问删除堆中任意元素是指把堆中优先级更高的元素全部删掉,然后删除指定元素,然后再把删掉的优先级更高的元素加回来,是这个意思吗?
发表于 2020-09-30 23:42:38 回复(0)
import java.util.*;
//接口
interface IService{
    public Object delete(Object obj);//抽象方法
}
//主类
public class Main{
    public static void main(String[] args){

    }
}

发表于 2019-03-21 21:38:04 回复(0)
太难了,根本不会
发表于 2019-03-14 01:24:49 回复(0)
void deleteElement(int *head,int index,int len)
{
    int t,a,b,c;
    mutx.lock;
    head[index]=head[len];  //删除指点元素;
    len--;
    a=0;
    while(index*2<=len && a==0)  //左子节点存在
    {
        c=index;    //存储节点号
        if(head[index]>head[2*index])   //值大于左子节点
        {
            a=head[index];    //交换值
            head[index]=head[2*index];    
            c=2*index;        //存储最大值对应的节点号
        
        }
        if((index*2+1)<=len)    //右子节点存在
        {
            if(head[index]>head[2*index+1])  //值大于右子节点
            {
                a=head[index];    //交换值
                head[index]=head[2*index+1];    
                head[2*index+1]=a;
                c=2*index+1;      //存储最大值对应的节点号
            }
        
        }
        if(c==index)//该节点比左右两个字数的值都小,,未进入过if循环,结束循环    
        {
            a=1;         
        }
        index=c;
    }

    mutx.ulock;
}
发表于 2018-10-19 18:07:19 回复(0)
 

发表于 2017-08-24 20:54:44 回复(0)
java.util.concurrent.PriorityBlockingQueue;
发表于 2017-07-28 12:50:07 回复(0)