Optimize slow heap implementation

The goal of my program is to implement a limited size heap , whose entries are just numbers. To set the priority of each element, it is necessary to search when it will repeat again for the first time. The higher the priority, the higher the heap tree it should be (the element with the highest priority is the root).
Assuming the heap has a size 2:
- The first two elements are added
- To add the third element, it is necessary to remove the heap element with higher priority and free space for the third element
Example:
0 1 2 2 1
The priority of the first 0 is a large enough number since it is not repeated, from 1 is 5, from 2 is 4.
The priority of the second 1 and 2 respectively: a large enough number because they no longer repeat.
Obs : If there were another 2, the priority of the last 2 would be 6.
Heap elements in order of interaction assuming it is size 2
1) 0 1 2) 1 2
3) 1 2
4) 1 2 (In this case it does not matter who the root is)

The problem is: Implemented and this program is slow for 10000 entries, how to optimize ? To find where the next element of X repeats, assuming that the position of X is [Xo], I run the whole vector from [Xo + 1] until I find the first element (I know the size of the vector then only 1 malloc ).

Program parts that I assume have the greatest complexities, especially the setRemoveMaximo functions that guarantees heap ownership and the previously described changePriority function in which the item > element.quantity is the priority.

/* Ajusta para que continue sendo heap apos a remocao da raiz */
void ajustarRemocaoMaximo(ElementoCache **pointerHeap){
    ElementoCache *heap = *pointerHeap;
    int pos = 1;
    if(pos*2 < tamanhoCache && ((2*pos)+1) < tamanhoCache){
        if(((2*pos)+1) >= tamanhoCache){
            if(heap[pos].quantidade < heap[pos*2].quantidade){
                ElementoCache *maiorFilho = &heap[2*pos];
                ElementoCache paiTemp = heap[pos];
                heap[pos] = *maiorFilho;
                *maiorFilho = paiTemp;
            }
            return ;
        }

        while(heap[pos].quantidade < heap[pos*2].quantidade || heap[pos].quantidade < heap[(2*pos)+1].quantidade){
            //if(heap[2*pos].elemento == -1)
            //    break;
            ElementoCache *maiorFilho;
            int posFilho = 0;
            if((heap[2*pos].quantidade > heap[(2*pos)+1].quantidade) || (heap[2*pos].quantidade == heap[(2*pos)+1].quantidade)){
                maiorFilho = &heap[2*pos];
                posFilho = 2*pos;
            }else if(heap[2*pos].quantidade < heap[(2*pos)+1].quantidade){
                maiorFilho = &heap[(2*pos)+1];
                posFilho = (2*pos)+1;
            }
            ElementoCache paiTemp = heap[pos];
            heap[pos] = *maiorFilho;
            *maiorFilho = paiTemp;
            pos = posFilho;
            if(pos >= (tamanhoCache-1) || (pos*2) >= (tamanhoCache-1)) break;
        }
    }
}

/* Verificar se determinado elemento esta no heap e o substitui */
int contemElemento(ElementoCache elemento, ElementoCache **pointerHeap){
    ElementoCache *heap = *pointerHeap;
    int i = 0;
    for(i = 1; i < tamanhoCache; i++){
        if(heap[i].elemento == elemento.elemento){
            heap[i] = elemento;
            return 1;
        }
    }
    return 0;
}

void alterarPrioridade(ElementoCache **pointElementos, int tamanho){
    ElementoCache *elementos = *pointElementos;
    int i = 0;
    int j = 0;
    for(i = 0; i < tamanho; i++){
        for(j = i+1; j < tamanho; j++){
            if(elementos[i].elemento == elementos[j].elemento){
                elementos[i].quantidade = j;
                break;
            }
            elementos[i].quantidade = 10001;
        }
    }
}

/* Ira inserir o elemento na ultima posicao do array e ajustar de acordo com a prioridade. O heap possuir -1 como elemento significa que eh uma posicao vazia */
void adicionarElemento(ElementoCache heap[], ElementoCache item){
    //Buscar primeira posicao vazia
    int i = 1;
    int contemPosicaoVazia = 0;
    if(heap[i].elemento == -1){
        heap[1] = item;
        contador++;
    }else{

        //Verificar se o elemento ja esta no heap
        if(contemElemento(item, &heap) == 1){
            ajustarRemocaoMaximo(&heap);
            return ;
        }
        int posicaoVazia = 0;
        for(i = 2; i < tamanhoCache; i++){
            if(heap[i].elemento == -1){
                contemPosicaoVazia = 1;
                posicaoVazia = i;
                break;
            }
        }
        //Tornar o maximo sempre a raiz da arvore
        if(contemPosicaoVazia == 1){
            heap[posicaoVazia] = item;
            contador++;
            if((posicaoVazia/2) != 0){ //FIXME: Posicao vazia nunca sera 0
                //Verifica se o filho eh maior que o pai
                while((heap[posicaoVazia].quantidade > heap[posicaoVazia/2].quantidade)){
                    ElementoCache temporario = heap[posicaoVazia/2];
                    heap[posicaoVazia/2] = heap[posicaoVazia];
                    heap[posicaoVazia] = temporario;
                    posicaoVazia = posicaoVazia/2;
                    if(posicaoVazia == 1) break;
                }
            }
        }else{
            //Remover a raiz da arvore. A nova raiz deve ser o ultimo elemento do heap
            heap[1] = heap[tamanhoCache-1];
            heap[tamanhoCache-1].elemento = -1;
            heap[tamanhoCache-1].quantidade = 0;
            ajustarRemocaoMaximo(&heap);
            adicionarElemento(heap, item);
        }
    }
}

void lerSolicitacoes(ElementoCache heap[], InfoCache *informacoes){
    int i = 0;
    for(i = 0; i < informacoes->qtdSolicitacoes; i++){
        adicionarElemento(heap, informacoes->elementos[i]);
    }
}