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

[问答题]

设计接口并且实现一个多线程安全的堆，并且要求可以删除堆中任意元素（非堆顶元素），要求尽量高效，假设已有标准的mutex实现可以使用。

Holiday_12138

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)

啊啊啊62

各位大神，这里的堆指的是大根堆、小根堆的那个（heap），还是堆栈的那个堆（stack）啊？

也就是我要不要有重建大根堆或小根堆的操作？

发表于 2017-08-24 11:12:25 回复(3)

牛客-68

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)

牛客792645054号

我想问删除堆中任意元素是指把堆中优先级更高的元素全部删掉，然后删除指定元素，然后再把删掉的优先级更高的元素加回来，是这个意思吗？

发表于 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)

大龄30IT男

太难了，根本不会

发表于 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)