Optimize slow heap deployment

Question

The goal of my program is to implement a heap of limited size, 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, in the higher levels of 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, you need to remove the heap element with higher priority and free up space for the third element
Example:
0 1 2 2 1
The priority of the first 0 is a large enough number since it does not repeat, from 1 is 5, from 2 is 4.
The priority of the second 1 and 2 respectively: a large enough number as they do not repeat more.
Obs: If there was one more number two, the priority of the last two would be six.
Elements of the heap in order of interaction assuming it has size 2
1) 0 1
2) 1 2
3) 1 2
4) 1 2 (In this case it matters little who is the root)

The problem is: I implemented and this program is slow to 10000 entries, how to optimize? To search where the next element of X repeats, assuming that the position of X is [Xo] I path all the vector going from [Xo+1] until finding the first element (I know the size of the vector so it is only done 1 malloc).

Parts of the program that I assume have the greatest complexities, especially the functions adjust which guarantees the heap property and the function described above change the value of in which item quantity element. 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]);
    }
}