// 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;
}
*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){
if(n == 0 && k ==0)
break;
max = INT_MIN;
struct MyDS *myDS = createMyDS(k);
for(int i = 0 ; i < n ; 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;
}
}
//deleteMin(myDS);
//Delete(myDS, 10);
//findMax(myDS);
//findMin(myDS);
}
return 0;
}