fork download

copy

// C program for efficient data structure
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
 
// A node of doubly linked list
struct LNode
{
    int data;
    int minHeapIndex;
    int maxHeapIndex;
    struct LNode *next, *prev;
};
 
// Structure for a doubly linked list
struct List
{
    struct LNode *head;
};
 
// Structure for min heap
struct MinHeap
{
    int size;
    int capacity;
    struct LNode* *array;
};
 
// Structure for max heap
struct MaxHeap
{
    int size;
    int capacity;
    struct LNode* *array;
};
 
// The required data structure
struct MyDS
{
    struct MinHeap* minHeap;
    struct MaxHeap* maxHeap;
    struct List* list;
};
 
// Function to swap two integers
void swapData(int* a, int* b)
{ int t = *a;   *a = *b;   *b = t; }
 
// Function to swap two List nodes
void swapLNode(struct LNode** a, struct LNode** b)
{ struct LNode* t = *a; *a = *b; *b = t; }
 
// A utility function to create a new List node
struct LNode* newLNode(int data)
{
    struct LNode* node =
    (struct LNode*) malloc(sizeof(struct LNode));
    node->minHeapIndex = node->maxHeapIndex = -1;
    node->data = data;
    node->prev = node->next = NULL;
    return node;
}
 
// Utility function to create a max heap of given capacity
struct MaxHeap* createMaxHeap(int capacity)
{
    struct MaxHeap* maxHeap =
    (struct MaxHeap*) malloc(sizeof(struct MaxHeap));
    maxHeap->size = 0;
    maxHeap->capacity = capacity;
    maxHeap->array =
    (struct LNode**) malloc(maxHeap->capacity * sizeof(struct LNode*));
    return maxHeap;
}
 
// Utility function to create a min heap of given capacity
struct MinHeap* createMinHeap(int capacity)
{
    struct MinHeap* minHeap =
    (struct MinHeap*) malloc(sizeof(struct MinHeap));
    minHeap->size = 0;
    minHeap->capacity = capacity;
    minHeap->array =
    (struct LNode**) malloc(minHeap->capacity * sizeof(struct LNode*));
    return minHeap;
}
 
// Utility function to create a List
struct List* createList()
{
    struct List* list =
    (struct List*) malloc(sizeof(struct List));
    list->head = NULL;
    return list;
}
 
// Utility function to create the main data structure
// with given capacity
struct MyDS* createMyDS(int capacity)
{
    struct MyDS* myDS =
    (struct MyDS*) malloc(sizeof(struct MyDS));
    myDS->minHeap = createMinHeap(capacity);
    myDS->maxHeap = createMaxHeap(capacity);
    myDS->list = createList();
    return myDS;
}
 
// Some basic operations for heaps and List
int isMaxHeapEmpty(struct MaxHeap* heap)
{  return (heap->size == 0); }
 
int isMinHeapEmpty(struct MinHeap* heap)
{  return heap->size == 0; }
 
int isMaxHeapFull(struct MaxHeap* heap)
{  return heap->size == heap->capacity; }
 
int isMinHeapFull(struct MinHeap* heap)
{  return heap->size == heap->capacity; }
 
int isListEmpty(struct List* list)
{  return !list->head;   }
 
int hasOnlyOneLNode(struct List* list)
{    return !list->head->next && !list->head->prev; }
 
 
// The standard minheapify function.  The only thing it does extra
// is swapping indexes of heaps inside the List
void minHeapify(struct MinHeap* minHeap, int index)
{
    int smallest, left, right;
    smallest = index;
    left = 2 * index + 1;
    right = 2 * index + 2;
 
    if ( minHeap->array[left] &&
        left < minHeap->size &&
        minHeap->array[left]->data < minHeap->array[smallest]->data
        )
        smallest = left;
 
    if ( minHeap->array[right] &&
        right < minHeap->size &&
        minHeap->array[right]->data < minHeap->array[smallest]->data
        )
        smallest = right;
 
    if (smallest != index)
    {
        // First swap indexes inside the List using address
        // of List nodes
        swapData(&(minHeap->array[smallest]->minHeapIndex),
                 &(minHeap->array[index]->minHeapIndex));
 
        // Now swap pointers to List nodes
        swapLNode(&minHeap->array[smallest],
                  &minHeap->array[index]);
 
        // Fix the heap downward
        minHeapify(minHeap, smallest);
    }
}
 
// The standard maxHeapify function.  The only thing it does extra
// is swapping indexes of heaps inside the List
void maxHeapify(struct MaxHeap* maxHeap, int index)
{
    int largest, left, right;
    largest = index;
    left = 2 * index + 1;
    right = 2 * index + 2;
 
    if ( maxHeap->array[left] &&
        left < maxHeap->size &&
        maxHeap->array[left]->data > maxHeap->array[largest]->data
        )
        largest = left;
 
    if ( maxHeap->array[right] &&
        right < maxHeap->size &&
        maxHeap->array[right]->data > maxHeap->array[largest]->data
        )
        largest = right;
 
    if (largest != index)
    {
        // First swap indexes inside the List using address
        // of List nodes
        swapData(&maxHeap->array[largest]->maxHeapIndex,
                 &maxHeap->array[index]->maxHeapIndex);
 
        // Now swap pointers to List nodes
        swapLNode(&maxHeap->array[largest],
                  &maxHeap->array[index]);
 
        // Fix the heap downward
        maxHeapify(maxHeap, largest);
    }
}
 
// Standard function to insert an item in Min Heap
void insertMinHeap(struct MinHeap* minHeap, struct LNode* temp)
{
    if (isMinHeapFull(minHeap))
        return;
 
    ++minHeap->size;
    int i = minHeap->size - 1;
    while (i && temp->data < minHeap->array[(i - 1) / 2]->data )
    {
        minHeap->array[i] = minHeap->array[(i - 1) / 2];
        minHeap->array[i]->minHeapIndex = i;
        i = (i - 1) / 2;
    }
 
    minHeap->array[i] = temp;
    minHeap->array[i]->minHeapIndex = i;
}
 
// Standard function to insert an item in Max Heap
void insertMaxHeap(struct MaxHeap* maxHeap, struct LNode* temp)
{
    if (isMaxHeapFull(maxHeap))
        return;
 
    ++maxHeap->size;
    int i = maxHeap->size - 1;
    while (i && temp->data > maxHeap->array[(i - 1) / 2]->data )
    {
        maxHeap->array[i] = maxHeap->array[(i - 1) / 2];
        maxHeap->array[i]->maxHeapIndex = i;
        i = (i - 1) / 2;
    }
 
    maxHeap->array[i] = temp;
    maxHeap->array[i]->maxHeapIndex = i;
}
 
 
// Function to find minimum value stored in the main data structure
int findMin(struct MyDS* myDS)
{
    if (isMinHeapEmpty(myDS->minHeap))
        return INT_MAX;
 
    return myDS->minHeap->array[0]->data;
}
 
// Function to find maximum value stored in the main data structure
int findMax(struct MyDS* myDS)
{
    if (isMaxHeapEmpty(myDS->maxHeap))
        return INT_MIN;
 
    return myDS->maxHeap->array[0]->data;
}
 
// A utility function to remove an item from linked list
void removeLNode(struct List* list, struct LNode** temp)
{
    if (hasOnlyOneLNode(list))
        list->head = NULL;
 
    else if (!(*temp)->prev) // first node
    {
        list->head = (*temp)->next;
        (*temp)->next->prev = NULL;
    }
    // any other node including last
    else
    {
        (*temp)->prev->next = (*temp)->next;
        // last node
        if ((*temp)->next)
            (*temp)->next->prev = (*temp)->prev;
    }
    free(*temp);
    *temp = NULL;
}
 
// Function to delete maximum value stored in the main data structure
void deleteMax(struct MyDS* myDS)
{
    MinHeap *minHeap = myDS->minHeap;
    MaxHeap *maxHeap = myDS->maxHeap;
 
    if (isMaxHeapEmpty(maxHeap))
        return;
    struct LNode* temp = maxHeap->array[0];
 
    // delete the maximum item from maxHeap
    maxHeap->array[0] =
    maxHeap->array[maxHeap->size - 1];
    --maxHeap->size;
    maxHeap->array[0]->maxHeapIndex = 0;
    maxHeapify(maxHeap, 0);
 
    // remove the item from minHeap
    minHeap->array[temp->minHeapIndex] = minHeap->array[minHeap->size - 1];
    --minHeap->size;
    minHeap->array[temp->minHeapIndex]->minHeapIndex = temp->minHeapIndex;
    minHeapify(minHeap, temp->minHeapIndex);
 
    // remove the node from List
    removeLNode(myDS->list, &temp);
}
 
// Function to delete minimum value stored in the main data structure
void deleteMin(struct MyDS* myDS)
{
    MinHeap *minHeap = myDS->minHeap;
    MaxHeap *maxHeap = myDS->maxHeap;
 
    if (isMinHeapEmpty(minHeap))
        return;
    struct LNode* temp = minHeap->array[0];
 
    // delete the minimum item from minHeap
    minHeap->array[0] = minHeap->array[minHeap->size - 1];
    --minHeap->size;
    minHeap->array[0]->minHeapIndex = 0;
    minHeapify(minHeap, 0);
 
    // remove the item from maxHeap
    maxHeap->array[temp->maxHeapIndex] = maxHeap->array[maxHeap->size - 1];
    --maxHeap->size;
    maxHeap->array[temp->maxHeapIndex]->maxHeapIndex = temp->maxHeapIndex;
    maxHeapify(maxHeap, temp->maxHeapIndex);
 
    // remove the node from List
    removeLNode(myDS->list, &temp);
}
 
// Function to enList an item to List
void insertAtHead(struct List* list, struct LNode* temp)
{
    if (isListEmpty(list))
        list->head = temp;
 
    else
    {
        temp->next = list->head;
        list->head->prev = temp;
        list->head = temp;
    }
}
 
// Function to delete an item from List. The function also
// removes item from min and max heaps
void Delete(struct MyDS* myDS, int item)
{
    MinHeap *minHeap = myDS->minHeap;
    MaxHeap *maxHeap = myDS->maxHeap;
 
    if (isListEmpty(myDS->list))
        return;
 
    // search the node in List
    struct LNode* temp = myDS->list->head;
    while (temp && temp->data != item)
        temp = temp->next;
 
    // if item not found
    if (!temp || temp && temp->data != item)
        return;
 
    // remove item from min heap
    minHeap->array[temp->minHeapIndex] = minHeap->array[minHeap->size - 1];
    --minHeap->size;
    minHeap->array[temp->minHeapIndex]->minHeapIndex = temp->minHeapIndex;
    minHeapify(minHeap, temp->minHeapIndex);
 
    // remove item from max heap
    maxHeap->array[temp->maxHeapIndex] = maxHeap->array[maxHeap->size - 1];
    --maxHeap->size;
    maxHeap->array[temp->maxHeapIndex]->maxHeapIndex = temp->maxHeapIndex;
    maxHeapify(maxHeap, temp->maxHeapIndex);
 
    // remove node from List
    removeLNode(myDS->list, &temp);
}
 
// insert operation for main data structure
void Insert(struct MyDS* myDS, int data)
{
    struct LNode* temp = newLNode(data);
 
    // insert the item in List
    insertAtHead(myDS->list, temp);
 
    // insert the item in min heap
    insertMinHeap(myDS->minHeap, temp);
 
    // insert the item in max heap
    insertMaxHeap(myDS->maxHeap, temp);
}
 
int main()
{
    int n, k;
    int arr[500010];
    int max;
    while(1){
        scanf("%d%d", &n, &k);
 
        if(n == 0 && k ==0)
            break;
        max = INT_MIN;
        struct MyDS *myDS = createMyDS(k);
 
        for(int i = 0 ; i < n ; i++){
            scanf("%d", &arr[i]);
        }
 
        for(int i = 0 ;i < k ; i++ ){
            Insert(myDS, arr[i]);
            int tmp = findMax(myDS) - findMin(myDS);
            if( tmp > max){
                max = tmp;
            }
        }
 
        for(int i = k ;i < n ; i ++){
            Delete(myDS, arr[i - k]);
            Insert(myDS, arr[i]);
            //printf("arr[i - k ] : %d  ,  findMax(myDS) : %d,  findMin(myDS) : %d\n", arr[i - k ], findMax(myDS) , findMin(myDS));
            int tmp = findMax(myDS) - findMin(myDS);
            if( tmp > max){
                max = tmp;
            }
        }
 
        printf("%d\n", max);
        //deleteMin(myDS);
        //Delete(myDS, 10);
        //findMax(myDS);
        //findMin(myDS);
 
        free(myDS);
 
    }
    return 0;
}

prog.c: In function ‘deleteMax’:
prog.c:286:5: error: unknown type name ‘MinHeap’
     MinHeap *minHeap = myDS->minHeap;
     ^~~~~~~
prog.c:286:5: note: use ‘struct’ keyword to refer to the type
prog.c:286:24: warning: initialization from incompatible pointer type [-Wincompatible-pointer-types]
     MinHeap *minHeap = myDS->minHeap;
                        ^~~~
prog.c:287:5: error: unknown type name ‘MaxHeap’
     MaxHeap *maxHeap = myDS->maxHeap;
     ^~~~~~~
prog.c:287:5: note: use ‘struct’ keyword to refer to the type
prog.c:287:24: warning: initialization from incompatible pointer type [-Wincompatible-pointer-types]
     MaxHeap *maxHeap = myDS->maxHeap;
                        ^~~~
prog.c:289:24: warning: passing argument 1 of ‘isMaxHeapEmpty’ from incompatible pointer type [-Wincompatible-pointer-types]
     if (isMaxHeapEmpty(maxHeap))
                        ^~~~~~~
prog.c:110:5: note: expected ‘struct MaxHeap *’ but argument is of type ‘int *’
 int isMaxHeapEmpty(struct MaxHeap* heap)
     ^~~~~~~~~~~~~~
prog.c:291:33: error: request for member ‘array’ in something not a structure or union
     struct LNode* temp = maxHeap->array[0];
                                 ^~
prog.c:294:12: error: request for member ‘array’ in something not a structure or union
     maxHeap->array[0] =
            ^~
prog.c:295:12: error: request for member ‘array’ in something not a structure or union
     maxHeap->array[maxHeap->size - 1];
            ^~
prog.c:295:27: error: request for member ‘size’ in something not a structure or union
     maxHeap->array[maxHeap->size - 1];
                           ^~
prog.c:296:14: error: request for member ‘size’ in something not a structure or union
     --maxHeap->size;
              ^~
prog.c:297:12: error: request for member ‘array’ in something not a structure or union
     maxHeap->array[0]->maxHeapIndex = 0;
            ^~
prog.c:298:16: warning: passing argument 1 of ‘maxHeapify’ from incompatible pointer type [-Wincompatible-pointer-types]
     maxHeapify(maxHeap, 0);
                ^~~~~~~
prog.c:168:6: note: expected ‘struct MaxHeap *’ but argument is of type ‘int *’
 void maxHeapify(struct MaxHeap* maxHeap, int index)
      ^~~~~~~~~~
prog.c:301:12: error: request for member ‘array’ in something not a structure or union
     minHeap->array[temp->minHeapIndex] = minHeap->array[minHeap->size - 1];
            ^~
prog.c:301:49: error: request for member ‘array’ in something not a structure or union
     minHeap->array[temp->minHeapIndex] = minHeap->array[minHeap->size - 1];
                                                 ^~
prog.c:301:64: error: request for member ‘size’ in something not a structure or union
     minHeap->array[temp->minHeapIndex] = minHeap->array[minHeap->size - 1];
                                                                ^~
prog.c:302:14: error: request for member ‘size’ in something not a structure or union
     --minHeap->size;
              ^~
prog.c:303:12: error: request for member ‘array’ in something not a structure or union
     minHeap->array[temp->minHeapIndex]->minHeapIndex = temp->minHeapIndex;
            ^~
prog.c:304:16: warning: passing argument 1 of ‘minHeapify’ from incompatible pointer type [-Wincompatible-pointer-types]
     minHeapify(minHeap, temp->minHeapIndex);
                ^~~~~~~
prog.c:131:6: note: expected ‘struct MinHeap *’ but argument is of type ‘int *’
 void minHeapify(struct MinHeap* minHeap, int index)
      ^~~~~~~~~~
prog.c: In function ‘deleteMin’:
prog.c:313:5: error: unknown type name ‘MinHeap’
     MinHeap *minHeap = myDS->minHeap;
     ^~~~~~~
prog.c:313:5: note: use ‘struct’ keyword to refer to the type
prog.c:313:24: warning: initialization from incompatible pointer type [-Wincompatible-pointer-types]
     MinHeap *minHeap = myDS->minHeap;
                        ^~~~
prog.c:314:5: error: unknown type name ‘MaxHeap’
     MaxHeap *maxHeap = myDS->maxHeap;
     ^~~~~~~
prog.c:314:5: note: use ‘struct’ keyword to refer to the type
prog.c:314:24: warning: initialization from incompatible pointer type [-Wincompatible-pointer-types]
     MaxHeap *maxHeap = myDS->maxHeap;
                        ^~~~
prog.c:316:24: warning: passing argument 1 of ‘isMinHeapEmpty’ from incompatible pointer type [-Wincompatible-pointer-types]
     if (isMinHeapEmpty(minHeap))
                        ^~~~~~~
prog.c:113:5: note: expected ‘struct MinHeap *’ but argument is of type ‘int *’
 int isMinHeapEmpty(struct MinHeap* heap)
     ^~~~~~~~~~~~~~
prog.c:318:33: error: request for member ‘array’ in something not a structure or union
     struct LNode* temp = minHeap->array[0];
                                 ^~
prog.c:321:12: error: request for member ‘array’ in something not a structure or union
     minHeap->array[0] = minHeap->array[minHeap->size - 1];
            ^~
prog.c:321:32: error: request for member ‘array’ in something not a structure or union
     minHeap->array[0] = minHeap->array[minHeap->size - 1];
                                ^~
prog.c:321:47: error: request for member ‘size’ in something not a structure or union
     minHeap->array[0] = minHeap->array[minHeap->size - 1];
                                               ^~
prog.c:322:14: error: request for member ‘size’ in something not a structure or union
     --minHeap->size;
              ^~
prog.c:323:12: error: request for member ‘array’ in something not a structure or union
     minHeap->array[0]->minHeapIndex = 0;
            ^~
prog.c:324:16: warning: passing argument 1 of ‘minHeapify’ from incompatible pointer type [-Wincompatible-pointer-types]
     minHeapify(minHeap, 0);
                ^~~~~~~
prog.c:131:6: note: expected ‘struct MinHeap *’ but argument is of type ‘int *’
 void minHeapify(struct MinHeap* minHeap, int index)
      ^~~~~~~~~~
prog.c:327:12: error: request for member ‘array’ in something not a structure or union
     maxHeap->array[temp->maxHeapIndex] = maxHeap->array[maxHeap->size - 1];
            ^~
prog.c:327:49: error: request for member ‘array’ in something not a structure or union
     maxHeap->array[temp->maxHeapIndex] = maxHeap->array[maxHeap->size - 1];
                                                 ^~
prog.c:327:64: error: request for member ‘size’ in something not a structure or union
     maxHeap->array[temp->maxHeapIndex] = maxHeap->array[maxHeap->size - 1];
                                                                ^~
prog.c:328:14: error: request for member ‘size’ in something not a structure or union
     --maxHeap->size;
              ^~
prog.c:329:12: error: request for member ‘array’ in something not a structure or union
     maxHeap->array[temp->maxHeapIndex]->maxHeapIndex = temp->maxHeapIndex;
            ^~
prog.c:330:16: warning: passing argument 1 of ‘maxHeapify’ from incompatible pointer type [-Wincompatible-pointer-types]
     maxHeapify(maxHeap, temp->maxHeapIndex);
                ^~~~~~~
prog.c:168:6: note: expected ‘struct MaxHeap *’ but argument is of type ‘int *’
 void maxHeapify(struct MaxHeap* maxHeap, int index)
      ^~~~~~~~~~
prog.c: In function ‘Delete’:
prog.c:354:5: error: unknown type name ‘MinHeap’
     MinHeap *minHeap = myDS->minHeap;
     ^~~~~~~
prog.c:354:5: note: use ‘struct’ keyword to refer to the type
prog.c:354:24: warning: initialization from incompatible pointer type [-Wincompatible-pointer-types]
     MinHeap *minHeap = myDS->minHeap;
                        ^~~~
prog.c:355:5: error: unknown type name ‘MaxHeap’
     MaxHeap *maxHeap = myDS->maxHeap;
     ^~~~~~~
prog.c:355:5: note: use ‘struct’ keyword to refer to the type
prog.c:355:24: warning: initialization from incompatible pointer type [-Wincompatible-pointer-types]
     MaxHeap *maxHeap = myDS->maxHeap;
                        ^~~~
prog.c:366:23: warning: suggest parentheses around ‘&&’ within ‘||’ [-Wparentheses]
     if (!temp || temp && temp->data != item)
                  ~~~~~^~~~~~~~~~~~~~~~~~~~~
prog.c:370:12: error: request for member ‘array’ in something not a structure or union
     minHeap->array[temp->minHeapIndex] = minHeap->array[minHeap->size - 1];
            ^~
prog.c:370:49: error: request for member ‘array’ in something not a structure or union
     minHeap->array[temp->minHeapIndex] = minHeap->array[minHeap->size - 1];
                                                 ^~
prog.c:370:64: error: request for member ‘size’ in something not a structure or union
     minHeap->array[temp->minHeapIndex] = minHeap->array[minHeap->size - 1];
                                                                ^~
prog.c:371:14: error: request for member ‘size’ in something not a structure or union
     --minHeap->size;
              ^~
prog.c:372:12: error: request for member ‘array’ in something not a structure or union
     minHeap->array[temp->minHeapIndex]->minHeapIndex = temp->minHeapIndex;
            ^~
prog.c:373:16: warning: passing argument 1 of ‘minHeapify’ from incompatible pointer type [-Wincompatible-pointer-types]
     minHeapify(minHeap, temp->minHeapIndex);
                ^~~~~~~
prog.c:131:6: note: expected ‘struct MinHeap *’ but argument is of type ‘int *’
 void minHeapify(struct MinHeap* minHeap, int index)
      ^~~~~~~~~~
prog.c:376:12: error: request for member ‘array’ in something not a structure or union
     maxHeap->array[temp->maxHeapIndex] = maxHeap->array[maxHeap->size - 1];
            ^~
prog.c:376:49: error: request for member ‘array’ in something not a structure or union
     maxHeap->array[temp->maxHeapIndex] = maxHeap->array[maxHeap->size - 1];
                                                 ^~
prog.c:376:64: error: request for member ‘size’ in something not a structure or union
     maxHeap->array[temp->maxHeapIndex] = maxHeap->array[maxHeap->size - 1];
                                                                ^~
prog.c:377:14: error: request for member ‘size’ in something not a structure or union
     --maxHeap->size;
              ^~
prog.c:378:12: error: request for member ‘array’ in something not a structure or union
     maxHeap->array[temp->maxHeapIndex]->maxHeapIndex = temp->maxHeapIndex;
            ^~
prog.c:379:16: warning: passing argument 1 of ‘maxHeapify’ from incompatible pointer type [-Wincompatible-pointer-types]
     maxHeapify(maxHeap, temp->maxHeapIndex);
                ^~~~~~~
prog.c:168:6: note: expected ‘struct MaxHeap *’ but argument is of type ‘int *’
 void maxHeapify(struct MaxHeap* maxHeap, int index)
      ^~~~~~~~~~

Standard output is empty